WordSearch [source code]
public class WordSearch {
static
/******************************************************************************/
class Solution {
static int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public boolean exist(char[][] board, String word) {
if (board.length == 0 || board[0].length == 0)
return false;
int R = board.length, C = board[0].length;
if (R * C < word.length ())
return false;
if (word.length () == 0)
return true;
char[] chs = word.toCharArray ();
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (dfs (board, chs, 0, i, j, new boolean[R][C]))
return true;
return false;
}
boolean dfs (char[][] board, char[] chs, int pos, int x, int y, boolean[][] used) {
if (board[x][y] != chs[pos])
return false;
if (pos == chs.length - 1)
return true;
used[x][y] = true;
for (int[] direction : directions) {
int nx = x + direction[0], ny = y + direction[1];
if (isValid (board, nx, ny, used) && dfs (board, chs, pos + 1, nx, ny, used))
return true;
}
used[x][y] = false; // critical: what do you do when you leave this path?
return false;
}
boolean isValid (char[][] board, int x, int y, boolean[][] used) {
return x >= 0 && x < board.length && y >= 0 && y < board[0].length && !used[x][y];
}
}
/******************************************************************************/
public static void main(String[] args) {
WordSearch.Solution tester = new WordSearch.Solution();
char[][][] boards = {
{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},
{{'a', 'a'}},
{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},
{{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}},
};
String[] words = {
"ABCCED",
"a",
"ABCB",
"ABCESEEEFS",
};
boolean[] answers = {
true,
true,
false,
true,
};
for (int i = 0; i < boards.length; i++) {
char[][] board = boards[i];
String word = words[i];
System.out.println (Printer.separator ());
boolean ans = answers[i], output = tester.exist (board, word);
System.out.printf ("%s and %s -> %s, expected: %b\n",
Matrix.printMatrix (board), word, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
除了DFS好像没有什么特别好的思路了? 这个问题干脆用BFS来写也可以, 反正也没有什么不可以;
另外, 这题没有说全都是大写字母还是全都是小写字母, 只说了是letter, 所以不要踩这个坑;
很丢人, 最后被test4给break掉了: 这题好像BFS不好写啊? 因为BFS是同时在处理好几个path, 所以几个path之间的used信息不好同步, 冲突了; 下面是这个失败的代码:
class Solution {
static int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public boolean exist(char[][] board, String word) {
if (board.length == 0 || board[0].length == 0)
return false;
int R = board.length, C = board[0].length;
if (R * C < word.length ())
return false;
if (word.length () == 0)
return true;
boolean[][] used;
Queue<Point> queue = new LinkedList<> ();
char[] chs = word.toCharArray ();
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if (board[i][j] == chs[0]) {
used = new boolean[R][C];
queue.offer (new Point (i, j));
// Definition: next position to match
int pos = 1;
if (chs.length == 1)
return true;
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int k = 0; k < size; k++) {
Point cur = queue.poll ();
used[cur.x][cur.y] = true;
for (int[] direction : directions) {
int x = cur.x + direction[0], y = cur.y + direction[1];
if (x >= 0 && x < R && y >= 0 && y < C && !used[x][y] && board[x][y] == chs[pos])
queue.offer (new Point (x, y));
}
}
// Just POS fall off right edge is not enough!
if (++pos == chs.length && !queue.isEmpty ())
return true;
}
}
return false;
}
static class Point {
int x, y;
Point (int x, int y) {this.x = x; this.y = y; }
public String toString () {
return String.format ("(%d, %d)", x, y);
}
}
}
打的倒是很快, 就是不对, 有点丢人;
感觉这题最后还是要用DFS来做; 另外这题叫不叫backtracking其实无所谓; 另外, 因为是一个boolean的search问题, 所以可能要用到一点global switch pruning的技巧? 明天早上再写了;
另外, 能不能总结一下为什么这题不能用BFS? 等于说这两者并不是任何时候都能通用的? 不对啊, BFS当中的used信息就真的是无法调和的吗? 我记得之前那个SwimmingInRisingWater的题目, 当时也是有一个seen的操作的啊;
所以其实这里反而又看出来那个题目的算法的牛逼之处了! 这么说来, 这种类DJ的算法, 其实跟BFS是有区别的; BFS是全面展开, 但是包括DJ还是swim算法, 最后其实虽然可能保留了好几条path, 但是同一个时间是尝试在extend某唯一的一条path;
感觉这个讲的太虚了, 不够准确; 会不会是这个原因? 我觉得这些个queue算法, 反正是肯定会同时走好几条path的, 那么一个问题是否适合用这种queue算法的一个决定性因素, 就是不同的path之间是否允许overlap? 这个感觉还是不够准确, 你怎么就知道swim那题不允许overlap?
回头想想, 好像当时对swim这题还真的其实没有理解透彻; 回头又去看了一下那题的代码, 那题其实是可以很安心的确定没有overlap的; 因为如果比如有一个path, 在被一个大cell挡住之后, 切换到了下一个path, 那么这个下一个path就不应该继续走过之前失败的这个path的任何一个cell, 因为nothing better will come out; 这里也就看出来当时那个PriorityQueue算法的厉害的地方: 首先, BFS走图, 肯定是要有一个seen的, 不然要回头; 但是我们这里说了, seen不是想用就能用的; 像这题, 允许path overlap的时候, 你用seen最后就直接把自己关了; 但是swim那题的厉害之处就是你接下来可以证明, 没有必要(不是不可能, 不允许, 是可以不允许)让path之间overlap, 所以就可以心安理得的用seen了;
当然, 这个问题在DFS的时候就没有了, seen随便用, 但是DFS并不能完成所有queue算法的操作, 比如swim那题, 我就没有看到过用DFS来做成功的人;
最后改成DFS就行了; 注意虽然我这里用的是returned recursion来避免了global switch这种pruning, 但是最后还是需要有一个undo这样的过程, 毕竟DFS本身本质上还是一条path一条path的探索, 当你上行退出当前path的时候, 肯定要undo到这些node的used的状态;
最后的速度是271ms (5%), 慢的很严重, 让我感觉这题是不是DFS不是最好的思路, 可能还有别的方向?
没有editorial;
Here accepted solution based on recursion. To save memory I decuded to apply bit mask for every visited cell. Please check board[y][x] ^= 256;
public boolean exist(char[][] board, String word) {
char[] w = word.toCharArray();
for (int y=0; y<board.length; y++) {
for (int x=0; x<board[y].length; x++) {
if (exist(board, y, x, w, 0)) return true;
}
}
return false;
}
private boolean exist(char[][] board, int y, int x, char[] word, int i) {
if (i == word.length) return true;
if (y<0 || x<0 || y == board.length || x == board[y].length) return false;
if (board[y][x] != word[i]) return false;
board[y][x] ^= 256;
boolean exist = exist(board, y, x+1, word, i+1)
|| exist(board, y, x-1, word, i+1)
|| exist(board, y+1, x, word, i+1)
|| exist(board, y-1, x, word, i+1);
board[y][x] ^= 256;
return exist;
}
大概思路其实还是差不多的, 主要就是一个InPlace flag的使用; 注意, 因为所有的letter最多只有7位, 所以他这里选择一个第八位是1, 下面全是0的bitmask, 然后xor: 1xor任何东西都是invert, 0xor任何东西都是保留, 所以这个最后就是直接让这些char的未使用的最高位当成一个boolean来使用;
类似的一个做法:
public class Solution {
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++)
for(int j = 0; j < board[0].length; j++){
if(exist(board, i, j, word, 0))
return true;
}
return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
if(ind == word.length()) return true;
if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
return false;
board[i][j]='*';
boolean result = exist(board, i-1, j, word, ind+1) ||
exist(board, i, j-1, word, ind+1) ||
exist(board, i, j+1, word, ind+1) ||
exist(board, i+1, j, word, ind+1);
board[i][j] = word.charAt(ind);
return result;
}
}
My java code use similar idea.
restriction is ‘*’ cannot be present in the input char matrix.
这里利用了一个性质, 因为之前old的char实际上我们是知道的: 在word里面(因为如果mismatch, 都不会走到set visited这一步), 所以直接可以改成一个不可能让向下的node match的char就行了;
复杂度:
I think the time complexity is (mn*4^k) where k is the length of the string; mn for for loop and for the dfs method its 4^k. Since the dfs method goes only as deep as the word length we have T(k)=4(T(k-1))=4*4T(k-2)=…=… which will be 4^k.
fanning^height, 这个应该很熟悉了; 如果让你证明, 就是用他这里这种类似等比公式的recurrence来证明;
InPlace永远的殇:
Your code works, but when your algorithm is running, board[][] is changed, which prevents it from concurrent usage.
所以严格来说, 实际上原来OP的这个bit的做法更加合理, 因为最起码只要对其他thread的read的方式进行一个修改(加一个&0x7F的mask), 那么其他thread最起码同时还能read;
I came up with a similar solution, but I return true immediately when I find the word successfully. No need to check the result after searching FOUR directions.
这个人的写法其实就跟我的一样, 他认为这种做法有premature exit而OP的没有; 实际上只能暴露了这个人自己的水平: OP的做法是有premature exit, 是通过OR本身的short circuiting来实现的; 这个做法其实在Pintos的原装代码里面见到过;
https://leetcode.com/problems/word-search/discuss/27811/My-Java-solution
public class Solution {
static boolean[][] visited;
public boolean exist(char[][] board, String word) {
visited = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
return true;
}
}
}
return false;
}
private boolean search(char[][]board, String word, int i, int j, int index){
if(index == word.length()){
return true;
}
if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
return false;
}
visited[i][j] = true;
if(search(board, word, i-1, j, index+1) ||
search(board, word, i+1, j, index+1) ||
search(board, word, i, j-1, index+1) ||
search(board, word, i, j+1, index+1)){
return true;
}
visited[i][j] = false;
return false;
}
}
好像还是差不多的思路;
https://leetcode.com/problems/word-search/discuss/27675/My-19ms-accepted-C++-code
class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
m=board.size();
n=board[0].size();
for(int x=0;x<m;x++)
for(int y=0;y<n;y++)
{
if(isFound(board,word.c_str(),x,y))
return true;
}
return false;
}
private:
int m;
int n;
bool isFound(vector<vector<char> > &board, const char* w, int x, int y)
{
if(x<0||y<0||x>=m||y>=n||board[x][y]=='\\0'||*w!=board[x][y])
return false;
if(*(w+1)=='\\0')
return true;
char t=board[x][y];
board[x][y]='\\0';
if(isFound(board,w+1,x-1,y)||isFound(board,w+1,x+1,y)||isFound(board,w+1,x,y-1)||isFound(board,w+1,x,y+1))
return true;
board[x][y]=t;
return false;
}
};
修改之前直接cache, 也行, 反正recursion做法;
https://leetcode.com/problems/word-search/discuss/27765/Java-DFS-solution-beats-97.64
public class Solution {
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
char[] chs = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(dfs(board, chs, 0, i, j)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, char[] words, int idx, int x, int y) {
if (idx == words.length) {
return true;
}
if (x < 0 || x == board.length || y < 0 || y == board[0].length) {
return false;
}
if (board[x][y] != words[idx]) {
return false;
}
board[x][y] ^= 256;
boolean exist = dfs(board, words, idx + 1, x, y + 1) ||
dfs(board, words, idx + 1, x, y - 1) || dfs(board, words, idx + 1, x + 1, y) ||
dfs(board, words, idx + 1, x - 1, y) ;
board[x][y] ^= 256;
return exist;
}
}
一样的;
submission最优解: 14(91):
class Solution {
public boolean exist(char[][] board, String word) {
if(board.length == 0 || board[0].length == 0) return false;
char[] array = word.toCharArray();
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if(board[i][j] == array[0]){
if(dfs(board, i, j, 0, array)) return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, int index, char[] word){
if(word.length == index) return true;
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word[index]) return false;
board[i][j] = '#'; //each letter could only be used once
boolean res = dfs(board, i+1, j, index + 1, word) || dfs(board, i-1, j, index + 1, word) || dfs(board, i, j+1, index + 1, word) || dfs(board, i, j-1, index + 1, word);
board[i][j] = word[index];
return res;
}
}
还是不理解为什么我的算法会慢这么多;
Problem Description
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
Difficulty:Medium
Total Accepted:164.5K
Total Submissions:590K
Contributor:LeetCode
Companies
facebookmicrosoftbloomberg
Related Topics
arraybacktracking
Similar Questions
Word Search II