? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。 |
?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
作者:Grey
原文地址:单词搜索系列问题
总体思路是:枚举从board的每个位置开始,看能否走出给定的单词,伪代码如下:
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (p(i, j, 0, str, board)) {
return true;
}
}
}
递归函数p
表示从board[i][j]
开始,能否走出str从0位置开始到最后的字符串。如果有任意一个路径满足条件,直接返回true即可。递归函数p
的base case是:
public static boolean p(int i, int j, int index, char[] str, char[][] board) {
if (index == str.length) {
return true;
}
if (i >= board.length || j >= board[0].length || i < 0 || j < 0 ) {
return false;
}
if (board[i][j] == '0') {
return false;
}
......
}
第一个if表示,如果index已经到str结尾了,说明我已经完成了str的完全匹配,直接返回true即可。
第二个if表示,如果index还没到str的结尾位置,但是i,j位置越界了,说明我的决策有问题,直接返回false。
第三个if表示,如果我当前的位置是曾经走过的位置,返回false。(因为我们为了防止走回头路,将走过的位置都标识为了0字符)
经过三个if,就是主要逻辑:
public static boolean p(int i, int j, int index, char[] str, char[][] board) {
.......
char c = board[i][j];
board[i][j] = '0';
if (str[index] == c) {
boolean p1 = p(i + 1, j, index + 1, str, board);
if (p1) {
board[i][j] = c;
return true;
}
boolean p2 = p(i, j + 1, index + 1, str, board);
if (p2) {
board[i][j] = c;
return true;
}
boolean p3 = p(i - 1, j, index + 1, str, board);
if (p3) {
board[i][j] = c;
return true;
}
boolean p4 = p(i, j - 1, index + 1, str, board);
if (p4) {
board[i][j] = c;
return true;
}
}
board[i][j] = c;
return false;
}
首先,将当前位置标识为了已走过,即
board[i][j] = '0'
接下来,只有在
str[index] == c
条件下(即:我当前位置需要匹配的字符正好是遍历到位置的字符),我才需要走四个方向的分支,四个分支,只要有一个分支完成任务,则无须走其他分支,直接返回true,四个分支都是false,则返回false。
完整代码见:
public class LeetCode\_0079\_WordSearch {
// 不能走重复路
public static boolean exist(char[][] board, String word) {
char[] str = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (p(i, j, 0, str, board)) {
return true;
}
}
}
return false;
}
public static boolean p(int i, int j, int index, char[] str, char[][] board) {
if (index == str.length) {
return true;
}
if (i >= board.length || j >= board[0].length || i < 0 || j < 0 ) {
return false;
}
if (board[i][j] == '0') {
return false;
}
char c = board[i][j];
board[i][j] = '0';
if (str[index] == c) {
boolean p1 = p(i + 1, j, index + 1, str, board);
if (p1) {
board[i][j] = c;
return true;
}
boolean p2 = p(i, j + 1, index + 1, str, board);
if (p2) {
board[i][j] = c;
return true;
}
boolean p3 = p(i - 1, j, index + 1, str, board);
if (p3) {
board[i][j] = c;
return true;
}
boolean p4 = p(i, j - 1, index + 1, str, board);
if (p4) {
board[i][j] = c;
return true;
}
}
board[i][j] = c;
return false;
}
}
总体思路是:枚举从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 ans
来存储所有走出的单词是哪些;
其次,我需要一个变量List 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 pre, List 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 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 pre, List 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 pre) {
LinkedList 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 findWords(char[][] board, String[] words){
Set set = new HashSet<>();
Trie trie = new Trie();
for (String word : words) {
if (!set.contains(word)){
set.add(word);
buildTrie(trie,word);
}
}
LinkedList pre= new LinkedList<>();
List 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 pre, List 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 pre) {
LinkedList 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;
}
}