D****6
发帖数: 278 | 1 这题我看大多人都是DFS, 那时间是exponential 4^n（n is the length of the
target word）吗？ | D****6
发帖数: 278 | | c******a
发帖数: 789 | 3 大小测试都过了
public boolean exist(char[][] board, String word) {
if (board==null || board.length==0 || board[0].length==0) return
false;
for (int i=0; i
for (int j=0; j
if (board[i][j]==word.charAt(0)) {
boolean[][] used = new boolean[board.length][board[0].
length];
used[i][j] = true;
if (walk(board, i, j, word, 1, used)) return true;
}
}
}
return false;
}
public boolean walk(char[][] board, int x, int y, String word, int
nextChar, boolean[][] used) {
if (nextChar==word.length()) return true;
if (x>0) {
if (board[x-1][y]==word.charAt(nextChar) && !used[x-1][y]) {
used[x-1][y] = true;
if (walk(board, x-1, y, word, nextChar+1, used)) {return
true;}
else used[x-1][y] = false;
}
}
if (x
if (board[x+1][y]==word.charAt(nextChar) && !used[x+1][y]) {
used[x+1][y] = true;
if (walk(board, x+1, y, word, nextChar+1, used)) return true;
else used[x+1][y] = false;
}
}
if (y>0) {
if (board[x][y-1]==word.charAt(nextChar) && !used[x][y-1]) {
used[x][y-1] = true;
if (walk(board, x, y-1, word, nextChar+1, used)) return true;
else used[x][y-1] = false;
}
}
if (y
if (board[x][y+1]==word.charAt(nextChar) && !used[x][y+1]) {
used[x][y+1] = true;
if (walk(board, x ,y+1, word, nextChar+1, used)) return true;
else used[x][y+1] = false;
}
}
return false;
} | D****6
发帖数: 278 | 4 我只是不知道running time complexity,能说说吗？ | r*****e
发帖数: 792 | 5 怎么得出4^n的结论的？
假设搜索范围是MxN，每个位置作为起始点最多访问一次，对每个
起始点来说，顶多遍历整个range每个点一次，这么说就是M^2xN^2,再准确点
说，搜索的半径是L，L是string的长度，那就应该是MNL^2吧。
【在 D****6 的大作中提到】
: 这题我看大多人都是DFS, 那时间是exponential 4^n（n is the length of the
: target word）吗？
| D****6
发帖数: 278 | 6 为什么“对每个起始点来说，顶多遍历整个range每个点一次“。这就是个graph with
branching factor 4. | b****g
发帖数: 192 | 7 你楼上的意思是说访问过的grid就不能在访问了，所以每个grid就被使用一次。你的理
解可能是从每个grid向四个方向递归访问，如果不考虑访问过的不再访问，那确实是4^
N。但是你楼上使用了剪枝，所以时间复杂度会下降，所以每个grid最多被用一次，所
以“对每个起始点来说，顶多遍历整个range每个点一次“。你如果不问这个问题我也
意识不到剪枝能把复杂度从指数降到多项式。
with
【在 D****6 的大作中提到】
: 为什么“对每个起始点来说，顶多遍历整个range每个点一次“。这就是个graph with
: branching factor 4.
| b****g
发帖数: 192 | 8 你的walk函数的思路是先判断后递归：先判断grid是否被使用过、是否出界、是否跟
word匹配，然后再递归。
我最开始做的时候实现递归后判断，进入函数后在判断本次递归grid是否被使用过、是
否出界、是否跟word匹配。大testcase超时，我看了别人写的才意识到先判断后递归会
节省特别多的时间。
【在 c******a 的大作中提到】
: 大小测试都过了
: public boolean exist(char[][] board, String word) {
: if (board==null || board.length==0 || board[0].length==0) return
: false;
:
: for (int i=0; i: for (int j=0; j: if (board[i][j]==word.charAt(0)) {
: boolean[][] used = new boolean[board.length][board[0].
: length];
| s*****n
发帖数: 994 | 9 有人用dp做过这道题嘛？全是aaaaaa的test case runtime error
这么说dp比dfs慢？dp的复杂度是(m*n)*(m*n)*(m*n)貌似是慢于dfs
【在 D****6 的大作中提到】
: 这题我看大多人都是DFS, 那时间是exponential 4^n（n is the length of the
: target word）吗？
| s********u
发帖数: 1109 | 10 没看懂。搜索的time cost和有多少个点没什么关系吧，有多少个点不代表有多少条路
径啊。
准确的说的话，我认为应该是 N*（4^L)。
【在 r*****e 的大作中提到】
: 怎么得出4^n的结论的？
: 假设搜索范围是MxN，每个位置作为起始点最多访问一次，对每个
: 起始点来说，顶多遍历整个range每个点一次，这么说就是M^2xN^2,再准确点
: 说，搜索的半径是L，L是string的长度，那就应该是MNL^2吧。
|
|
