From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/word_search2.rs | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100644 other/word_search2.rs (limited to 'other/word_search2.rs') 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>; 26], + is_end: bool +} + +impl Solution { + pub fn find_words(board: Vec>, words: Vec) -> Vec { + 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>, trie: &mut Trie, pos: (usize, usize), s: &mut String, ans: &mut Vec) { + 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)); +} -- cgit v1.2.3