登录
  • #刷题
  • #leetcode

LC‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‍‌‍‍‍‍‍‍‍‌‍‍‍‌‍‌ 212 Trie 高赞答案解惑

yangmars
552
3
题目在这里: leetcode.com

看了最高赞的答案(答案附在下面了),有一点不太理解的地方,假如给定以下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) {[br]
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[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[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[j] = c;

}

public TrieNode buildTrie(String[] words) {[br]
TrieNode root = new TrieNode();

for (String w : words) {

TrieNode p = root;

for (char c : w.toCharArray()) {

int i = c - 'a';

if (p.next == null) p.next = new TrieNode();

p = p.next;

}

p.word = w;

}

return root;

}

class TrieNode {

TrieNode[] next = new TrieNode[26];

String word;

}
3条回复
热度排序

发表回复