LC 212 Trie 高赞答案解惑

题目在这里： https://leetcode.com/problems/word-search-ii/
看了最高赞的答案（答案附在下面了），有一点不太理解的地方，假如给定以下matrix和array
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]["oath","hello","eat","rain"]
那么按照下面答案的buildTrie(),  matrix里面的第一个字符"o"就会满足 p.word != null 的条件，因为”hello"的最后一个字符o.word=“hello”，所以 hello会被加入 res里面，但是答案是没有这个“hello"的，而且这个解法也是没问题的。我想问下大家，我是哪里理解错了呢？ 谢谢
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;
}

我觉得这份代码错误还挺多的。
这是我总结的版本 - github。
(好吧，原来是"[  i  ]"被解读成斜体的字符格式了lol)
dfs/backtrack方法里面，board的使用是有问题的,应该是board[  i  ] [j]。
buildTrie()方法里面，if(p.next[idx] = null) p.next[idx] = new TrieNode();

在buildTrie(String[] words)的时候，取一个word为例(为了避免混淆，我把此处的word写成WORD。而TrieNode里面的word字段仍然为word):
只有当某个该WORD走到底、也就是最后一个char的时候，对应的TrieNode的word字段才会被赋值成WORD，前面该WORD的所有字符(char)对应的TrieNode的word字段，都是String类型的默认初值，也就是null。
其目的就是标志该WORD在Trie里面已经搜索完整，可以用来判断。

本题使用String类型的word字段是一个很好的技巧，可以直接把word字段(的内容)拿来进行比较。


相比较而言，如果只是使用布尔类型的isWord就不具备这个功能。
这题目还涉及到单词的重复，为了避免重复加入到答案列表里面，直接把word字段再给抹除就不会被加入了。

zea7ot 发表于 2020-8-10 14:12
我觉得这份代码错误还挺多的。
这是我总结的版本 - github。
(好吧，原来是"[  i  ]"被解读成斜体的字符 ...

搞明白了，p=p.next[i], 会把指针往下挪一层， 多谢！

mark, will look later