aboutsummaryrefslogtreecommitdiff
path: root/other/word_search2.rs
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/word_search2.rs
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/word_search2.rs')
-rw-r--r--other/word_search2.rs59
1 files changed, 59 insertions, 0 deletions
diff --git a/other/word_search2.rs b/other/word_search2.rs
new file mode 100644
index 0000000..2c61941
--- /dev/null
+++ b/other/word_search2.rs
@@ -0,0 +1,59 @@
+#[derive(Default)]
+struct Solution;
+
+struct Trie {
+ child: [Option<Box<Trie>>; 26],
+ is_end: bool
+}
+
+impl Solution {
+ pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
+ let mut trie = Trie::default();
+ for w in words {
+ let mut node = &mut trie;
+ for u in w.bytes() {
+ node = node.child[(u - b'a') as usize].get_or_insert(Default::default());
+ }
+ node.is_end = true;
+ }
+ let (mut board, mut ans) = (board, Vec::new());
+ for i in 0..board.len() {
+ for j in 0..board[0].len() {
+ Self::backtrack(
+ &mut board,
+ &mut trie,
+ (i, j),
+ &mut String::new(),
+ &mut ans
+ );
+ }
+ }
+ ans
+ }
+ fn backtrack(board: &mut Vec<Vec<char>>, trie: &mut Trie, pos: (usize, usize), s: &mut String, ans: &mut Vec<String>) {
+ let c = board[pos.0][pos.1];
+ if let Some(node) = &mut trie.child[(c as u8 - b'a') as usize] {
+ s.push(c);
+ if node.is_end {
+ ans.push(s.clone());
+ node.is_end = false;
+ }
+ board[pos.0][pos.1] = '*';
+ for d in [0,1,0,!0,0].windows(2) {
+ let i = pos.0.wrapping_add(d[0]);
+ let j = pos.1.wrapping_add(d[1]);
+ if (0..board.len()).contains(&i) && (0..board[0].len()).contains(&j) && board[i][j] != '*' {
+ Self::backtrack(board, node, (i, j), s, ans);
+ }
+ }
+ board[pos.0][pos.1] = c;
+ s.pop();
+ }
+ }
+}
+
+fn main() {
+ let board = vec![vec!['a','b'], vec!['c','d']];
+ let words = vec!["abcb".to_string()];
+ print!("{:?}", Solution::find_words(board, words));
+}