LeetCode每日一题(212. Word Search II)

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
Output: [“eat”,“oath”]

Example 2:

Input: board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
Output: []

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

---

思路是抄的，代码是自己写的。整体来说就是反过来思考， 不要用 board 去检查 words， 而是要用 words 来检查 board， 但是 words 需要变一下形， 变成 trie 的形式， 然后遍历 board 中的每个 cell， dfs 检查从该 cell 出发，能在 trie 中走多远

---

#[derive(Clone)]
struct Node {
    nexts: Vec<Option<Node>>,
    word: Option<String>,
}

impl Node {
    fn new() -> Self {
        Self {
            nexts: vec![None; 26],
            word: None,
        }
    }

    fn add(&mut self, mut s: String, ori: String) {
        if s.is_empty() {
            self.word = Some(ori);
            return;
        }
        let c = s.remove(0);
        if let Some(n) = &mut self.nexts[c as usize - 97] {
            n.add(s, ori);
            return;
        }
        let mut n = Node::new();
        n.add(s, ori);
        self.nexts[c as usize - 97] = Some(n);
    }
}

impl Solution {
    fn dfs(board: &mut Vec<Vec<char>>, r: i32, c: i32, trie: &mut Node, ans: &mut Vec<String>) {
        if r < 0 || r >= board.len() as i32 || c < 0 || c >= board[0].len() as i32 {
            return;
        }
        if board[r as usize][c as usize] == '-' {
            return;
        }
        let chr = board[r as usize][c as usize];
        board[r as usize][c as usize] = '-';
        if let Some(next) = &mut trie.nexts[chr as usize - 97] {
            if let Some(w) = next.word.take() {
                ans.push(w);
            }
            Solution::dfs(board, r + 1, c, next, ans);
            Solution::dfs(board, r - 1, c, next, ans);
            Solution::dfs(board, r, c + 1, next, ans);
            Solution::dfs(board, r, c - 1, next, ans);
        }
        board[r as usize][c as usize] = chr;
    }
    pub fn find_words(mut board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
        let mut root = Node::new();
        for w in words {
            root.add(w.clone(), w);
        }
        let mut ans = Vec::new();
        for r in 0..board.len() {
            for c in 0..board[0].len() {
                Solution::dfs(&mut board, r as i32, c as i32, &mut root, &mut ans)
            }
        }
        ans
    }
}
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
60
61
62
63
64
65
66