Leetcode : Word Search
Diffculty：Medium
给一个char型的字符矩阵，给一个英文单词，尝试判断这个字符串，是否存在于这个字符矩阵中。
这里是否存在的含义，相当于沿着矩阵横纵中画一条线，按顺序找到该单词。一个位置的字符只允许使用一次（也就是说这条线不允许交叉）
举栗：
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
思路：
这是一个典型的使用回溯法的算法题。
可以逐个遍历矩阵中的字符去匹配，如果匹配到了单词中的第一个字符，那就从这个点出发，向上下左右四个方向去匹配第二个字符（当然已经走过的不能匹配，在我的算法里直接返回false），直到全部匹配到返回true，或者遍历完矩阵返回false。
每匹配到一个节点，那就记录该节点已经走过。继续往其他方向找下一个几点。
这里要注意的是，当接下来四个方向的节点都没找到时，那么该节点就要开始回溯，但是在回溯之前，需要把走过该节点的路径抹掉。（这里很重要，我一开始就在这事失误了）。
第一个是没有经过优化的。我使用了一个Set<String> 来存储走过的路径。但是很显然，有额外的空间开销，并且每次在 Set<String> 中判断是否走过路径，会很耗时。但是整体思路是正确的。
代码如下：
// leetcode 执行时间 80ms - beats 9.83%
public static boolean exist(char[][] board, String word) {
int height = board.length;
int width = board[0].length;
Set<String> searchPath = new HashSet<>();
for(int i=0; i<height; i++){
for(int j=0; j<width; j++){
boolean exist = searchChar(board,word,0,i,j, searchPath);
searchPath.clear();
if(exist){
return true;
}
}
}
return false;
}
private static boolean searchChar(char[][] board, String word, int index, int hIdx, int wIdx, Set<String> searchPath){
int height = board.length;
int width = board[0].length;
if(hIdx>=height || hIdx<0 || wIdx>=width || wIdx<0){
return false;
}
String path = hIdx + "_" + wIdx;
if(searchPath.contains(path)){
return false;
}
if(board[hIdx][wIdx] == word.charAt(index)){
searchPath.add(path); // 如果匹配，就暂时把已走过的路径加上
if(index == word.length() - 1){
return true;
}else{
boolean up = searchChar(board,word,index+1,hIdx-1,wIdx,searchPath);
if(up){
return true;
}
boolean down = searchChar(board,word,index+1,hIdx+1,wIdx,searchPath);
if(down){
return true;
}
boolean left = searchChar(board,word,index+1,hIdx,wIdx-1,searchPath);
if(left){
return true;
}
boolean right = searchChar(board,word,index+1,hIdx,wIdx+1,searchPath);
if(right){
return true;
}
}
searchPath.remove(path); // 如果接下来四个都没匹配，则该层会返回false。那么将该层path移除
}
return false;
}
由于上面时间太慢，我参考了一下其他人的写法。于是有了下面的改进版。
思路还是一样，只是在原来的坐标位置上，记录已经走过的标记。
由于是英文字母，我们可以将 board[x][y] -=26，当擦除路径时 +=26。（26是为了在运算以后离开英文字母的值域范围）实践证明这方法可行，执行时间提高到了9ms（beats 84.03%）
参考的那位原作者的方式是使用 了 异或 操作符。board[x][y] ^=256，擦除路径时再执行一遍 board[x][y] ^=256，就还原了。这是利用了位运算异或的特性，与同一个数字异或两次会回到原来的数字。所以这里不管异或什么数字都可以，但是要注意的是，异或之后的结果。要在'A'~'Z' 之外，所以以防万一，要么异或 256 要么异或 1。是最好的选择。
事实也证明了，异或运算比加减运算还要快。
使用异或运算，速度达到了 7ms（beats 100.0%）算是最快的了
代码如下：
// leetcode 7ms - beats 100.0%
public static boolean exist_v2(char[][] board, String word) {
int height = board.length;
int width = board[0].length;
for(int i=0; i<height; i++){
for(int j=0; j<width; j++){
boolean exist = searchChar_v2(board,word,0,i,j);
if(exist){
return true;
}
}
}
return false;
}
private static boolean searchChar_v2(char[][] board, String word, int index, int hIdx, int wIdx){
int height = board.length;
int width = board[0].length;
if(hIdx>=height || hIdx<0 || wIdx>=width || wIdx<0){
return false;
}
if(board[hIdx][wIdx] == word.charAt(index)){
// board[hIdx][wIdx] -= 26;
board[hIdx][wIdx] ^= 256;
if(index == word.length() - 1){
return true;
}else{
boolean up = searchChar_v2(board,word,index+1,hIdx-1,wIdx);
if(up){
return true;
}
boolean down = searchChar_v2(board,word,index+1,hIdx+1,wIdx);
if(down){
return true;
}
boolean left = searchChar_v2(board,word,index+1,hIdx,wIdx-1);
if(left){
return true;
}
boolean right = searchChar_v2(board,word,index+1,hIdx,wIdx+1);
if(right){
return true;
}
}
// board[hIdx][wIdx] += 26;
board[hIdx][wIdx] ^= 256;
}
return false;
}
网友评论