单词搜索题 求助

lintcode原题：

http://www.lintcode.com/zh-cn/problem/word-search/



给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。

单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。




样例
给出board =

[

  "ABCE",

  "SFCS",

  "ADEE"

]

word = "ABCCED"， ->返回 true,

word = "SEE"，-> 返回 true,

word = "ABCB"， -> 返回 false.






我是想用BFS，以word中的首字母依次作为起点，然后BFS。但是在路径保存时出了些问题，没想出来怎样修改，想请教一下大家，谢谢了。我定义的是x是水平方向，y是竖直方向。


public static boolean exist(char[][] board, String word) {
               
                boolean result = false;
                int[][] next = {{0,1},//右
                                            {1,0},//下
                                            {0,-1},//左
                                            {-1,0},//上
                };
                int[][] flag = new int [board.length][board[0].length];
               
                Queue<Node> queue = new LinkedList<>();  
                String s = "";
                int tx,ty;
                int startx,starty;
                int k;
                for(int i = 0; i < board.length; i++){
                        for(int j = 0; j < board[i].length; j++){
                                startx = j;
                                starty = i;
                               
                                if(board[i][j] == word.charAt(0)){

                                        Node start = new Node(startx,starty,board[i][j]+"");
                                        flag[i][j] = 1;
                                        queue.offer(start);
                                        while(!queue.isEmpty()){
                                                String str = queue.peek().s;
                                                s = s + str;
                                                int x = queue.peek().x;
                                                int y = queue.peek().y;
                                                queue.poll();
                                                for(k = 0; k <=3; k++){
                                                        tx = x + next[k][0];
                                                        ty = y + next[k][1];
                                                       
                                                        if(ty < 0 || ty > board.length-1 || tx < 0 || tx > board[ty].length-1 || flag[ty][tx] == 1){
                                                                continue;
                                                        }
                                                               
                                                        if(word.contains(s + board[ty][tx])){
                                                                Node node = new Node(tx,ty,board[ty][tx]+"");
                                                                queue.offer(node);
                                                                flag[ty][tx] = 1;
                                                        }
                                                       
                                                        if(s.equals(word)){
                                                                return true;
                                                        }

                                                }

                                        }
                                        for(int m = 0; m < flag.length; m++){
                                                for(int n = 0; n < flag[m].length; n++){
                                                        flag[m][n] = 0;
                                                }
                                        }
                                        s = "";
                                }

                        }
               
                }
               
                return result;
       
        }



class Node{
        int x;
        int y;
        String s;
        public Node(int x, int y, String s){
                this.x = x;
                this.y = y;
                this.s = s;
        }
}

这个题感觉用BFS是不是有点儿不太好实现啊？

这道题其实真不如用DFS做。用BFS做的话，你要自己维护每一条路径，代码会比较复杂而且容易出错。现场想一次无错是非常难的；另外就是这题BFS用并没有效率上的优势，因为无论是BFS还是DFS，都只需搜索到word.length()深度即可。所以，我觉得如果面试官没有限制的话，用DFS就好了。

水逼一枚 发表于 2015-7-18 12:03
这个题感觉用BFS是不是有点儿不太好实现啊？

嗯嗯，一开始只想了BFS

stellari 发表于 2015-7-18 13:37
这道题其实真不如用DFS做。用BFS做的话，你要自己维护每一条路径，代码会比较复杂而且容易出错。现场想一次 ...

谢谢，讲的太好了

stellari 发表于 2015-7-18 13:37
这道题其实真不如用DFS做。用BFS做的话，你要自己维护每一条路径，代码会比较复杂而且容易出错。现场想一次 ...

你好，想再请教下DFS的问题，能递归找到最终答案，但是终止条件和递归结束返回的问题一直没想明白，基础比较差，谢谢了。

public static boolean exist(char[][] board, String word) {
               
                boolean result = false;
               
                int[][] flag = new int [board.length][board[0].length];
                String s = "";
                for(int i = 0; i < board.length; i++){
                        for(int j = 0; j < board[i].length; j++){
                                if(board[i][j] == word.charAt(0)){
                                        flag[i][j] = 1;
                                        s = board[i][j] +"";
                                        result = dfs(j,i,s,word,board,flag);               
                                }
                               
                        }
                }
                       
                return result;
               
        }


public static boolean dfs(int x, int y, String s, String word, char[][] board, int[][]flag){
               
                boolean result = false;
                int[][] next = {{0,1},//右
                            {1,0},//下
                            {0,-1},//左
                            {-1,0},//上
                };
               
                int tx,ty,k;
               
                if(s.equals(word)){
                        result = true;
                }
               
                for(k = 0; k <=3; k++){

                        tx = x + next[k][0];
                        ty = y + next[k][1];
               
                        if(ty < 0 || ty > board.length-1 || tx < 0 || tx > board[ty].length-1 || flag[ty][tx] == 1){
                                continue;
                        }
                       
                        if(word.contains(s + board[ty][tx])){
                                String str = s;
                                s = s + board[ty][tx];
                                flag[ty][tx] = 1;
                                result = dfs(tx,ty,s,word,board,flag);
                                flag[ty][tx] = 0;
                                s = str;
                               
                        }
               
                }
               
                return result;
        }

int[][] next = {{0,1},//右
                            {1,0},//下
                            {0,-1},//左
                            {-1,0},//上
                };

有一个建议：这种从头到尾都不变的常量，可以定义成类的成员变量，如果作为局部变量定义在DFS函数里，会浪费很多空间的。另外，看见满篇的斜体字，楼主发现什么规律了么？中括号在这儿会被定义成类似html的标签，所以把代码用<>包起来吧。

zhuli19901106 发表于 2015-7-22 16:25
int[][] next = {{0,1},//右
                            {1,0},//下
                            {0,- ...

谢谢，这些都没意识到。。。能再帮我看下这个dfs函数的问题吗

你的代码里的flag{i}{j}都变成flag{j}了，用代码区域括起来吧。

大致看了下，代码中有两处问题
1. 你可以看DFS中的代码，flag{i}{j} = 1，flag{i}{j} = 0，这么回溯是对的，为什么在exist函数里就不回溯呢？这样就错了。
2. 这题只判断能否找到目标单词，所以DFS中的那个String s是多余的，没必要一路保存中间的那些单词前缀。你只要保存一个长度就行了。