s*****1
发帖数: 134 | 1 版上有没有做出leetcode online test 中我的 word search 的 java版，这题我java
版做了，能通过小规模测试，但大规模的通过不了，写了2个版本都超时了。
我的思路和网上搜索的c++版本（通过）的一样，就是一个点开始向四周辐射搜索，类
似于DFS，做DFS是需要一个二维的boolean矩阵来记录这个点是否visit过。我感觉就是
这个环节出了问题，C++深拷贝一个二维矩阵快吧，但是java深拷贝一个二维矩阵很费
时。
我的程序已经有DP和pre-check了，还是不快，望能够写出快速程序的大牛赐教，最好
贴代码 或站内头条，非常感谢！ | a***o
发帖数: 1182 | 2 C++搞个引用就行了，不用深拷贝，java不清楚
java
【在 s*****1 的大作中提到】
: 版上有没有做出leetcode online test 中我的 word search 的 java版，这题我java
: 版做了，能通过小规模测试，但大规模的通过不了，写了2个版本都超时了。
: 我的思路和网上搜索的c++版本（通过）的一样，就是一个点开始向四周辐射搜索，类
: 似于DFS，做DFS是需要一个二维的boolean矩阵来记录这个点是否visit过。我感觉就是
: 这个环节出了问题，C++深拷贝一个二维矩阵快吧，但是java深拷贝一个二维矩阵很费
: 时。
: 我的程序已经有DP和pre-check了，还是不快，望能够写出快速程序的大牛赐教，最好
: 贴代码 或站内头条，非常感谢！
| s*****1
发帖数: 134 | 3 谢谢，关于java的版本，大牛们回应一下吧！
不胜感激~ | T**********r
发帖数: 52 | 4 public boolean exist(char[][] board, String word) {
if(word == null || word.length() == 0){
return true;
}
char c = word.charAt(0);
for(int i = 0; i < board.length; i ++){
for(int j = 0; j < board[i].length; j ++){
if(board[i][j] ==c){
board[i][j] = 0;
if(dfs(board, i, j, word, 1)){
return true;
}
board[i][j] = c;
}
}
}
return false;
}
private boolean dfs(char[][] board, int row, int col, String word, int k) {
if(k == word.length()){
return true;
}
// int[][] dir = { {-1,-1}, {-1,0}, {-1,1}, {0,1}, // for 8
directions
// {1,1},{1,0},{1,-1},{0,-1}};
int[][] dir = { {-1,0}, {0,1}, {1,0},{0,-1}};
char c = word.charAt(k);
int M = board.length;
int N = board[0].length;
for(int[] d : dir){
int i = row + d[0];
int j = col + d[1];
if(0 <= i && i < M && 0 <= j && j < N && board[i][j] == c){
board[i][j] = 0;
if(dfs(board, i, j, word, k+1)){
return true;
}
board[i][j] = c;
}
}
return false;
} | s*****1
发帖数: 134 | | x******9
发帖数: 473 | 6 这个过大集合会超时，求教。
这个确实直接会爆掉
["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"], "
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
【在 T**********r 的大作中提到】
: public boolean exist(char[][] board, String word) {
: if(word == null || word.length() == 0){
: return true;
: }
:
: char c = word.charAt(0);
:
: for(int i = 0; i < board.length; i ++){
: for(int j = 0; j < board[i].length; j ++){
: if(board[i][j] ==c){
| k*********6
发帖数: 738 | 7 public class Solution {
public boolean exist(char[][] board, String word) {
// Start typing your Java solution below
// DO NOT write main() function
//DFS
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0|| board[0].length == 0)
return false;
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++)
{
for(int j = 0; j < board[0].length; j++)
{
if (board[i][j] == word.charAt(0))
{
visited[i][j] = true;
if (dfs(board, word, i, j, 1, visited)) return true;
visited[i][j] = false;
}
}
}
return false;
}
public boolean dfs(char[][] board, String word, int i, int j, int letter
, boolean[][]visited)
{
if (letter == word.length()) return true;
// check all positon around (i, j), to see if it is the same as word
.charAt(letter)
// (i - 1, j), (i + 1, j), (i, j -1), (i , j + 1)
char curr = word.charAt(letter);
if (i - 1 >= 0 && !visited[i -1][j] && board[i -1][j] == curr)
{
visited[i -1][j] = true;
if (dfs(board, word, i -1, j, letter + 1, visited)) return true;
visited[i -1][j] = false;
}
if (i + 1 < board.length &&!visited[i + 1][j] && board[i + 1][j] ==
curr)
{
visited[i + 1][j] = true;
if(dfs(board, word, i + 1, j, letter + 1, visited)) return true;
visited[i + 1][j] = false;
}
if (j - 1 >= 0 && !visited[i][j - 1] && board[i][j - 1] == curr)
{
visited[i][j - 1] = true;
if(dfs(board, word, i, j - 1, letter + 1, visited)) return true;
visited[i][j - 1] = false;
}
if (j + 1 < board[i].length && !visited[i][j + 1] && board[i][j + 1
] == curr)
{
visited[i][j + 1] = true;
if(dfs(board, word, i, j + 1, letter + 1, visited)) return true;
visited[i][j + 1] = false;
}
return false;
}
}
java
【在 s*****1 的大作中提到】
: 版上有没有做出leetcode online test 中我的 word search 的 java版，这题我java
: 版做了，能通过小规模测试，但大规模的通过不了，写了2个版本都超时了。
: 我的思路和网上搜索的c++版本（通过）的一样，就是一个点开始向四周辐射搜索，类
: 似于DFS，做DFS是需要一个二维的boolean矩阵来记录这个点是否visit过。我感觉就是
: 这个环节出了问题，C++深拷贝一个二维矩阵快吧，但是java深拷贝一个二维矩阵很费
: 时。
: 我的程序已经有DP和pre-check了，还是不快，望能够写出快速程序的大牛赐教，最好
: 贴代码 或站内头条，非常感谢！
| x******9
发帖数: 473 | 8 thx.
我的错，和4楼一样，但是在寻找下一层的时候赋值错误，他用的int j=col+d[i],我用
了col=col+d[i]，但是进去之前按理说已经置为其他字符了，我再仔细想想其中的区别。
【在 k*********6 的大作中提到】
: public class Solution {
: public boolean exist(char[][] board, String word) {
: // Start typing your Java solution below
: // DO NOT write main() function
: //DFS
: if (word == null || word.length() == 0) return true;
: if (board == null || board.length == 0|| board[0].length == 0)
: return false;
:
: boolean[][] visited = new boolean[board.length][board[0].length];
| z****e
发帖数: 54598 | 9 public class Solution {
public boolean exist(char[][] board, String word) {
// Start typing your Java solution below
// DO NOT write main() function
if(word.length()<1) return false;
for(int i=0;i
for(int j=0;j
if(board[i][j]==word.charAt(0)){
board[i][j] = ' ';
if(this.existed(board,word.substring(1),i,j)
) return true;
board[i][j] = word.charAt(0);
}
}
}
return false;
}
private boolean existed(char[][] board, String word, int i, int j){
if(word.length()==0) return true;
int[][] m = {{1,0},{-1,0},{0,1},{0,-1}};
for(int k =0;k
int ii=m[k][0]+i;
int jj=m[k][1]+j;
if(ii=0
&&jj=0
&&board[ii][jj]==word.charAt(0)){
board[ii][jj] = ' ';
if(existed(board,word.substring(1),ii,jj)) return
true;
board[ii][jj] = word.charAt(0);
}
}
return false;
}
} | c***d
发帖数: 26 | 10 这题野蛮暴力就能通过大case呀。
public class Solution {
public boolean exist(char[][] board, String word) {
// Start typing your Java solution below
// DO NOT write main() function
if (board==null) return false;
boolean visited[][] = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if (helper(board, visited, word, i, j, 0)) return true;
}
}
return false;
}
private boolean helper(char[][] board, boolean[][] visited, String word,
int i, int j, int index) {
if (i<0 || i>= board.length || j<0 || j>=board[0].length) return
false;
if (board[i][j] != word.charAt(index)) return false;
if (visited[i][j]) return false;
if (index == word.length() - 1) return true;
visited[i][j] = true;
boolean exist = helper(board, visited, word, i-1, j, index+1)
|| helper(board, visited, word, i, j+1, index+1)
|| helper(board, visited, word, i+1, j, index+1)
|| helper(board, visited, word, i, j-1, index+1);
visited[i][j] = false;
return exist;
}
}
java
【在 s*****1 的大作中提到】
: 版上有没有做出leetcode online test 中我的 word search 的 java版，这题我java
: 版做了，能通过小规模测试，但大规模的通过不了，写了2个版本都超时了。
: 我的思路和网上搜索的c++版本（通过）的一样，就是一个点开始向四周辐射搜索，类
: 似于DFS，做DFS是需要一个二维的boolean矩阵来记录这个点是否visit过。我感觉就是
: 这个环节出了问题，C++深拷贝一个二维矩阵快吧，但是java深拷贝一个二维矩阵很费
: 时。
: 我的程序已经有DP和pre-check了，还是不快，望能够写出快速程序的大牛赐教，最好
: 贴代码 或站内头条，非常感谢！
| l*n
发帖数: 529 | 11 大牛追求就是不一样啊，连memoization都是不浪费空间的。
j)
【在 z****e 的大作中提到】
: public class Solution {
: public boolean exist(char[][] board, String word) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(word.length()<1) return false;
: for(int i=0;i: for(int j=0;j: if(board[i][j]==word.charAt(0)){
: board[i][j] = ' ';
: if(this.existed(board,word.substring(1),i,j)
|
|
