aboutsummaryrefslogtreecommitdiff
path: root/word_search2.rs
blob: 2c619410e54a15ab4d067b3a8a70d1668afd4c02 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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));
}