tries

jhideki · jhideki · commit 7628e872ac81 · 2024-04-23T18:16:43.000-07:00
diff --git a/src/construct_tree.rs b/src/construct_tree.rs
@@ -0,0 +1,19 @@
+use crate::TreeNode;
+use std::cell::RefCell;
+use std::rc::Rc;
+pub struct Solution {}
+impl Solution {
+    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
+        if preorder.is_empty() || inorder.is_empty() {
+            return None;
+        }
+
+        let mid = inorder.iter().position(|&x| x == preorder[0]).unwrap();
+        let root_node = Rc::new(RefCell::new(TreeNode::new(preorder[0])));
+        let left = Self::build_tree(preorder[1..=mid].to_vec(), inorder[..mid].to_vec());
+        let right = Self::build_tree(preorder[mid + 1..].to_vec(), inorder[mid..].to_vec());
+        root_node.borrow_mut().left = left;
+        root_node.borrow_mut().right = right;
+        Some(root_node)
+    }
+}
diff --git a/src/implement_trie.rs b/src/implement_trie.rs
@@ -0,0 +1,42 @@
+use std::collections::HashMap;
+pub struct Trie {
+    children: HashMap<char, Trie>,
+    end: bool,
+}
+impl Trie {
+    fn new() -> Self {
+        Trie {
+            end: false,
+            children: HashMap::new(),
+        }
+    }
+    fn insert(&mut self, word: String) {
+        let mut cur = self;
+        for c in word.chars() {
+            cur = cur.children.entry(c).or_insert(Trie::new());
+        }
+        cur.end = true;
+    }
+    fn starts_with(&self, prefix: String) -> bool {
+        let mut cur = self;
+        for c in prefix.chars() {
+            if cur.children.contains_key(&c) {
+                cur = cur.children.get(&c).unwrap();
+            } else {
+                return false;
+            }
+        }
+        true
+    }
+    fn search(&self, word: String) -> bool {
+        let mut cur = self;
+        for c in word.chars() {
+            if let Some(node) = cur.children.get(&c) {
+                cur = node;
+            } else {
+                return false;
+            }
+        }
+        cur.end
+    }
+}
diff --git a/src/kth_largest_stream.rs b/src/kth_largest_stream.rs
@@ -0,0 +1,25 @@
+use std::cmp::Reverse;
+use std::collections::BinaryHeap;
+struct KthLargest {
+    nums: Vec<i32>,
+    k: i32,
+    heap: BinaryHeap<Reverse<i32>>,
+}
+impl KthLargest {
+    fn new(k: i32, nums: Vec<i32>) -> Self {
+        let mut heap = BinaryHeap::new();
+        for val in nums {
+            heap.push(Reverse(val));
+            if heap.len() > k as usize {
+                heap.pop();
+            }
+        }
+        println!("{:?}", heap);
+        KthLargest { nums, k, heap }
+    }
+    fn add(&mut self, val: i32) -> i32 {
+        self.heap.push(Reverse(val));
+        self.heap.pop().unwrap();
+        self.heap.peek().unwrap().0
+    }
+}
diff --git a/src/main.rs b/src/main.rs
@@ -1,7 +1,7 @@
-mod kth_smallest_bst;
-use kth_smallest_bst::Solution;
+mod word_search2;
 use std::cell::RefCell;
 use std::rc::Rc;
+use words_dictionary;
 #[derive(Debug, PartialEq, Eq)]
 pub struct TreeNode {
     pub val: i32,
diff --git a/src/max_path_sum.rs b/src/max_path_sum.rs
@@ -0,0 +1,22 @@
+use crate::TreeNode;
+use std::cell::RefCell;
+use std::rc::Rc;
+pub struct Solution {}
+impl Solution {
+    pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
+        fn rec(root: Option<Rc<RefCell<TreeNode>>>, max: &mut i32) -> i32 {
+            if let Some(node) = root {
+                let node = node.borrow();
+                let left = rec(node.left.clone(), max).max(0);
+                let right = rec(node.right.clone(), max).max(0);
+                let split = left + right + node.val;
+                *max = std::cmp::max(*max, split);
+                return node.val + std::cmp::max(left, right);
+            }
+            0
+        }
+
+        let mut max = i32::MIN;
+        std::cmp::max(rec(root, &mut max), max)
+    }
+}
diff --git a/src/serialize_deserialize_bt.rs b/src/serialize_deserialize_bt.rs
@@ -0,0 +1,42 @@
+use crate::TreeNode;
+use std::cell::RefCell;
+use std::rc::Rc;
+pub struct Codec {}
+impl Codec {
+    fn new() -> Self {}
+    fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
+        self.preorder(root)
+    }
+    fn preorder(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
+        let mut res = String::new();
+        if let Some(node) = root {
+            let node = node.borrow();
+            res.push_str(&node.val.to_string());
+            res.push(',');
+            res.push_str(&self.preorder(node.left.clone()));
+            res.push_str(&self.preorder(node.right.clone()));
+            return res;
+        }
+        "null,".to_string()
+    }
+
+    fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
+        let parts: Vec<&str> = data.split(',').collect();
+        println!("{:?}", parts);
+        fn rec(parts: &Vec<&str>, i: &mut usize) -> Option<Rc<RefCell<TreeNode>>> {
+            let val = parts[*i];
+            if parts[*i] == "null" {
+                *i += 1;
+                return None;
+            }
+            let mut node = Rc::new(RefCell::new(TreeNode::new(val.parse().unwrap())));
+            *i += 1;
+            let left = rec(parts, i);
+            let right = rec(parts, i);
+            node.borrow_mut().left = left;
+            node.borrow_mut().right = right;
+            Some(node)
+        }
+        rec(&parts, &mut 0)
+    }
+}
diff --git a/src/word_search2.rs b/src/word_search2.rs
@@ -0,0 +1,85 @@
+pub struct Solution {}
+use std::collections::{HashMap, HashSet};
+pub struct Trie {
+    end: bool,
+    children: HashMap<char, Trie>,
+}
+impl Trie {
+    fn new() -> Self {
+        Trie {
+            end: false,
+            children: HashMap::new(),
+        }
+    }
+    fn insert(&mut self, word: String) {
+        let mut cur = self;
+        for c in word.chars() {
+            let cur = cur.children.entry(c).or_insert(Trie::new());
+        }
+        cur.end = true;
+    }
+}
+impl Solution {
+    pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
+        let mut root = Trie::new();
+        for w in words {
+            root.insert(w);
+        }
+        let mut visted: HashSet<(i32, i32)> = HashSet::new();
+        let mut res: Vec<String> = Vec::new();
+        fn dfs(
+            row: i32,
+            col: i32,
+            node: &mut Trie,
+            word: &str,
+            board: &Vec<Vec<char>>,
+            res: &mut Vec<String>,
+            visited: &mut HashSet<(i32, i32)>,
+        ) {
+            if row < 0
+                || col < 0
+                || row as usize == board.len()
+                || col as usize == board[0].len()
+                || visited.contains(&(row, col))
+                || !node
+                    .children
+                    .contains_key(&board[row as usize][col as usize])
+            {
+                return;
+            }
+            visited.insert((row, col));
+
+            let mut cur = node
+                .children
+                .get_mut(&board[row as usize][col as usize])
+                .unwrap();
+            let mut new_word = word.to_string();
+            new_word.push(board[row as usize][col as usize]);
+            println!("{:?}", word);
+            if cur.end {
+                res.push(new_word.clone());
+            }
+            dfs(row + 1, col, &mut cur, &new_word, board, res, visited);
+            dfs(row + 1, col, &mut cur, &new_word, board, res, visited);
+            dfs(row, col + 1, &mut cur, &new_word, board, res, visited);
+            dfs(row, col - 1, &mut cur, &new_word, board, res, visited);
+            visited.remove(&(row, col));
+        }
+        let mut word = String::new();
+        for r in 0..board.len() {
+            for c in 0..board[0].len() {
+                let mut word: Vec<char> = Vec::new();
+                dfs(
+                    r as i32,
+                    c as i32,
+                    &mut root,
+                    &"",
+                    &board,
+                    &mut res,
+                    &mut visted,
+                );
+            }
+        }
+        res
+    }
+}
diff --git a/src/words_dictionary.rs b/src/words_dictionary.rs
@@ -0,0 +1,54 @@
+use std::collections::HashMap;
+
+struct WordDictionary {
+    children: HashMap<char, WordDictionary>,
+    end: bool,
+}
+
+/**
+ * `&self` means the method takes an immutable reference.
+ * If you need a mutable reference, change it to `&mut self` instead.
+ */
+impl WordDictionary {
+    fn new() -> Self {
+        WordDictionary {
+            children: HashMap::new(),
+            end: false,
+        }
+    }
+
+    fn add_word(&mut self, word: String) {
+        let mut cur = self;
+        for c in word.chars() {
+            cur = cur.children.entry(c).or_insert(WordDictionary::new());
+        }
+        cur.end = true;
+    }
+
+    fn search(&self, word: String) -> bool {
+        fn dfs(root: &WordDictionary, word: String) -> bool {
+            let mut cur = root;
+            let mut i = 0;
+            for c in word.chars() {
+                if c == '.' {
+                    for node in cur.children.values() {
+                        let word = &word[i + 1..];
+                        if dfs(node, word.to_string()) {
+                            return true;
+                        }
+                    }
+                    return false;
+                }
+                if let Some(val) = cur.children.get(&c) {
+                    cur = val;
+                } else {
+                    return false;
+                }
+                i += 1;
+            }
+            cur.end
+        }
+        dfs(self, word)
+    }
+}
+
