m********l
发帖数: 791 | 1 了解这题DFS的话代码简洁而且大测试不超时。
就是想拿这题练习一下BFS的解法，自己吭哧吭哧写的代码超时了，不知道代码中的哪
一步太耗时？大家帮忙看一下，谢谢~
或者其他可以改进的地方大家也不妨指出~
代码如下：
public class Solution {
public static Queue queue = new LinkedList();
public boolean exist(char[][] board, String word) {
if (word.equals("") || word == null)
return true;
if (board == null || board.length == 0)
return false;
int row = board.length;
int col = board[0].length;
String tmp = word; // save complete word for repeated use
boolean[][] visited;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
word = tmp;
visited = new boolean[row][col]; // refresh visited at
beginning of every new iteration
if (board[i][j] == word.charAt(0)) {
word = word.substring(1);
if (word.length() == 0) return true;
Cell cell = new Cell(i, j);
queue.offer(cell);
visited[i][j] = true;
if (bfs(board, word, visited)) {
return true;
}
}
}
}
return false;
}
public boolean bfs(char[][] board, String word, boolean[][] visited) {
int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
while (!queue.isEmpty()) {
Cell tmp = queue.poll();
int x = tmp.row;
int y = tmp.col;
for (int k = 0; k < 4; k++) {
int i = x + dir[k][0];
int j = y + dir[k][1];
if (i >= 0 && j >= 0 && i < board.length && j < board[0].
length && board[i][j] == word.charAt(0) && !visited[i][j]) {
word = word.substring(1);
if (word.length() == 0) return true;
Cell cell = new Cell(i, j);
queue.offer(cell);
visited[i][j] = true;
}
}
}
return false;
}
static class Cell {
int row;
int col;
public Cell (int row, int col) {
this.row = row;
this.col = col;
}
}
} | | | c*******2
发帖数: 60 | | m********l
发帖数: 791 | 3 代码在OJ上跑过，就是在大测试的时候显示Time Limit Exceeded
我觉得BFS 和 DFS 的time complexity应该是一样，不应该一个通过另一个没通过吧。
觉得代码里哪里应该有点小问题。
【在 c*******2 的大作中提到】
: 怎么感觉这个BFS是错的呢...
| m********l
发帖数: 791 | 4 我看了一下，原来的代码是有错。我加了一行break；应该可以了。
但是还是无法通过大测试，不知道到底是哪里太慢了。我的理解是BFS和DFS 在时间复
杂度上应该是差不多的呀
【在 c*******2 的大作中提到】
: 怎么感觉这个BFS是错的呢...
| t******d
发帖数: 1383 | 5 optimal bst ?那个词汇频率来建造bst的那个题目么 |
|
