单词搜索问题 - Grey Zeng
source link: https://www.cnblogs.com/greyzeng/p/16321675.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
作者：Grey
原文地址：单词搜索问题
题目链接#
思路#
总体思路是：枚举从board的每个位置开始，看能走出哪些单词表中的单词，伪代码如下：
for (int i = 0; i < board.length;i++) {
for (int j = 0; j < board[0].length;j++) {
int size = process(i,j, board, words);
if (size == words.size) {
return new ArrayList<>(words);
}
}
}
递归函数process 表示从board[i][j]出发，能走出哪些单词表中的单词。返回值是能走出的单词数量是多少，如果返回值正好等于单词表的数量，不需要继续尝试了，直接返回可以走出所有单词。
如果要达到上述目的，这个递归函数还差哪些参数呢？
首先，我需要一个List<String> ans来存储所有走出的单词是哪些；
其次，我需要一个变量List<Character> pre存储我每次走到的字符串是什么；
最后，我需要一个快速判断走的是不是无效路径的数据结构，因为如果我没有这个数据结构，我每走一步都需要暴力枚举我走出的pre是不是在单词表中。例如，假设单词表为：
[apple, banana]
假设一个3 x 5的board为：
['a','p','p','l','e']
['a','x','y','b','a']
['b','a','n','a','n']
如果我即将走的下一个字符是第二行第二列的x字符，这个数据结构可以快速帮我过滤掉这种情况，没必要从x字符继续往下走了。
这个数据结构就是前缀树，通过前缀树，可以很快找到某个字符串是否是一个单词的前缀，同时，也可以很快得出某个字符串是否已经完成了匹配。
完善后的递归函数完整签名如下：
// 从board的i，j位置出发，
// 走过的路径保存在pre中，
// 收集到的单词表中的单词保存在ans中
// trie就是单词表建立的前缀树
int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie)
在整个递归调用之前，我们需要最先构造前缀树，前缀树的定义如下：
public static class Trie {
public Trie[] next;
public int pass;
public boolean end;
public Trie() {
// 由于只有26个小写字母，所以只需要准备26大小的数组即可。
next = new Trie[26];
// 遍历过的字符次数
pass = 0;
// 是否是一个字符串的结尾
end = false;
}
}
针对单词表，我们建立前缀树，过程如下：
Set<String> set = new HashSet<>();
Trie trie = new Trie();
for (String word : words) {
if (!set.contains(word)){
set.add(word);
buildTrie(trie,word);
}
}
之所以要定义Set，是因为想把单词表去重，buildTrie的完整代码如下，以下为前缀树创建的经典代码，有路则复用，无路则创建，循环结束后，将end设置为true，表示这个单词的结束标志：
private static void buildTrie(Trie trie, String word) {
char[] str = word.toCharArray();
for (char c : str) {
if (trie.next[c - 'a'] == null) {
trie.next[c - 'a'] = new Trie();
}
trie = trie.next[c - 'a'];
trie.pass++;
}
trie.end = true;
}
任何一个字符x，如果：
trie.next[x - 'a'] == null || trie.next[x - 'a'].pass == 0;
则表示没有下一个方向上的路，或者下一个方向上的字符已经用过了，这种情况下，就直接可以无需继续从这个字符开始尝试。
到了某个字符，如果：
trie.end = true
表示这个字符已经是满足条件的某个单词的结尾了，可以开始收集答案。
前缀树准备好了以后，就可以考虑递归函数的base case了，
public static int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie){
if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
return 0;
}
if (board[i][j] == '0') {
// 不走回头路
return 0;
}
if (trie.next[board[i][j] - 'a'] == null || trie.next[board[i][j] - 'a'].pass == 0) {
// 没有路可以走
return 0;
}
...
}
第一个if表示越界，显然返回0，因为你的决策已经让i，j越界了，决策错了，返回0没毛病。
第三个if表示的情况，就是前面说的，前缀树判断当前位置已经没有继续尝试的必要了，返回0也没毛病。
由于题目要求不能走回头路，所以我将走过的位置上的字符修改为字符0，标识我走过这里了，所以第二个if表示：如果我们决策到某个位置是0,说明我们走了回头路，返回0也没毛病。
如果顺利通过了上述三个if，那么说明当前决策的位置有利可图，说不定就可以走出单词表中的单词，所以把当前位置的字符加入pre,表示我已经选择了当前字符，请去上下左右四个方向帮我收集答案，代码如下：
pre.addLast(c);
trie = trie.next[index];
int fix = 0;
if(trie.end) {
ans.add(buildString(pre));
trie.end=false;
fix++;
}
// 这句表示：先标识一下当前位置为0字符，表示我已经走过了
board[i][j] = '0';
// 以下四行表示：
// 请去上，下，左，右四个方向帮我收集答案吧。
fix +=process(i+1,j,pre,ans,board,trie);
fix+=process(i,j+1,pre,ans,board,trie);
fix+=process(i-1,j,pre,ans,board,trie);
fix+=process(i,j-1,pre,ans,board,trie);
// 深度优先遍历的恢复现场操作。
board[i][j] = c;
pre.pollLast();
trie.pass-=fix;
其中if(trie.end)说明已经走出了一个符合条件的单词，可以收集答案了。buildString(pre)就是把之前收集的字符拼接成一个字符串，代表已经拼凑出来的那个单词：
private static String buildString(LinkedList<Character> pre) {
LinkedList<Character> preCopy = new LinkedList<>(pre);
StringBuilder sb = new StringBuilder();
while (!preCopy.isEmpty()) {
Character c = preCopy.pollFirst();
sb.append(c);
}
return sb.toString();
}
完整代码#
public class LeetCode_0212_WordSearchII {
public static class Trie {
public Trie[] next;
public int pass;
public boolean end;
public Trie() {
next = new Trie[26];
pass = 0;
end = false;
}
}
public static List<String> findWords(char[][] board, String[] words){
Set<String> set = new HashSet<>();
Trie trie = new Trie();
for (String word : words) {
if (!set.contains(word)){
set.add(word);
buildTrie(trie,word);
}
}
LinkedList<Character> pre= new LinkedList<>();
List<String> ans = new ArrayList<>();
for (int i = 0; i < board.length;i++) {
for (int j = 0; j < board[0].length;j++) {
int times = process(i,j,pre,ans,board,trie);
if (times == set.size()) {
return new ArrayList<>(set);
}
}
}
return ans;
}
public static int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie){
if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
return 0;
}
char c = board[i][j];
if (c == '0') {
// 不走回头路
return 0;
}
int index= c - 'a';
if (trie.next[index] == null || trie.next[index].pass == 0) {
// 没有路可以走
return 0;
}
pre.addLast(c);
trie = trie.next[index];
int fix = 0;
if(trie.end) {
ans.add(buildString(pre));
trie.end=false;
fix++;
}
board[i][j] = '0';
fix +=process(i+1,j,pre,ans,board,trie);
fix+=process(i,j+1,pre,ans,board,trie);
fix+=process(i-1,j,pre,ans,board,trie);
fix+=process(i,j-1,pre,ans,board,trie);
board[i][j] = c;
pre.pollLast();
trie.pass-=fix;
return fix;
}
private static String buildString(LinkedList<Character> pre) {
LinkedList<Character> preCopy = new LinkedList<>(pre);
StringBuilder sb = new StringBuilder();
while (!preCopy.isEmpty()) {
Character c = preCopy.pollFirst();
sb.append(c);
}
return sb.toString();
}
private static void buildTrie(Trie trie, String word) {
char[] str = word.toCharArray();
for (char c : str) {
if (trie.next[c - 'a'] == null) {
trie.next[c - 'a'] = new Trie();
}
trie = trie.next[c - 'a'];
trie.pass++;
}
trie.end = true;
}
}
更多#
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK