一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 446|回复: 10
收起左侧

[算法题] 单词搜索题 求助

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-7-18 11:44:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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.length; j++){
                                startx = j;
                                starty = i;
                               
                                if(board[j] == word.charAt(0)){

                                        Node start = new Node(startx,starty,board[j]+"");
                                        flag[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;
        }
}


水逼一枚 发表于 2015-7-18 12:03:21 | 显示全部楼层
这个题感觉用BFS是不是有点儿不太好实现啊?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-18 13:37:26 | 显示全部楼层
这道题其实真不如用DFS做。用BFS做的话,你要自己维护每一条路径,代码会比较复杂而且容易出错。现场想一次无错是非常难的;另外就是这题BFS用并没有效率上的优势,因为无论是BFS还是DFS,都只需搜索到word.length()深度即可。所以,我觉得如果面试官没有限制的话,用DFS就好了。
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-7-18 15:06:28 | 显示全部楼层
水逼一枚 发表于 2015-7-18 12:03
这个题感觉用BFS是不是有点儿不太好实现啊?

嗯嗯,一开始只想了BFS
回复 支持 反对

使用道具 举报

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

谢谢,讲的太好了
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-7-18 16:47:55 | 显示全部楼层
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.length; j++){
                                if(board[j] == word.charAt(0)){
                                        flag[j] = 1;
                                        s = board[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;
        }
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-22 16:25:14 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-22 16:45 编辑

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

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

使用道具 举报

 楼主| jy_121 发表于 2015-7-22 16:44:47 | 显示全部楼层
zhuli19901106 发表于 2015-7-22 16:25
int[][] next = {{0,1},//右
                            {1,0},//下
                            {0,- ...

谢谢,这些都没意识到。。。能再帮我看下这个dfs函数的问题吗
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-22 16:48:25 | 显示全部楼层
你的代码里的flag{i}{j}都变成flag{j}了,用代码区域括起来吧。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-22 16:53:40 | 显示全部楼层
大致看了下,代码中有两处问题
1. 你可以看DFS中的代码,flag{i}{j} = 1,flag{i}{j} = 0,这么回溯是对的,为什么在exist函数里就不回溯呢?这样就错了。
2. 这题只判断能否找到目标单词,所以DFS中的那个String s是多余的,没必要一路保存中间的那些单词前缀。你只要保存一个长度就行了。
回复 支持 反对

使用道具 举报

 楼主| jy_121 发表于 2015-7-22 22:41:31 | 显示全部楼层
zhuli19901106 发表于 2015-7-22 16:53
大致看了下,代码中有两处问题
1. 你可以看DFS中的代码,flag{i}{j} = 1,flag{i}{j} = 0,这么回溯是对的 ...

谢谢你的解答啊!确实exist那里我忘了回溯。而且我都在一个点的回溯后加了如果result==true就直接返回true,之前的回溯确实有问题。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 05:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表