Java: 如何实现从二维数组中查找单词（单词搜索）？

Question

给定一个二维板和字典中的单词列表，我想找到板上的所有单词。

每个单词必须由连续相邻单元格的字母构成，其中 "adjacent" 单元格是水平或垂直相邻的单元格。同一字母单元格不能在一个单词中使用多次。

例如，给定 words = ["oath","pea","eat","rain"] 和棋盘 =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

并遇到了以下实现：

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[i][j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[i][j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res); 
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}

而在 buildTrie(String[] words) 中，在为特定单词设置 trie 之后，它会执行 p.word = w;。在 dfs(...) 中，它会检查 if (p.word != null)。

但是为什么 p.word 是 null 直到找到单词中的最后一个字符，然后 p.word 就不再是 null ？

p.word不依赖于任何索引，直接与对象本身相关，所以应该可以随时访问，只是不明白是怎么回事null 直到找到单词的最后一个字符。

谢谢

Answer 1

这是一个示例 trie：

考虑到上面的trie，在构建trie的过程中，默认情况下，每个节点的word都是null，除了它结束的节点。

例如，在上面的 trie 中插入 buy 时，我们扫描单词 buy 的每个字符并将其放在每个节点中。当我们到达最后一个字符 y 时，我们将 buy 放入该节点的 word 变量中。这就是为什么您会发现每个其他节点的 word 等于 null 除了它结束的节点。

Java: 如何实现从二维数组中查找单词（单词搜索）？

Java: How to implement finding a word from 2D array (word search)?

java

arrays

algorithm

trie

depth-first-search