一亩三分地论坛

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

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

[Leetcode] Word Ladder BFS总是过不了大数据是为何?求指点!

[复制链接] |试试Instant~ |关注本帖
liuwujijay 发表于 2016-4-9 00:13:13 | 显示全部楼层 |阅读模式

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

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

x
public class Solution {       
        List<String> ret ;
         
         public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
                 ret = new ArrayList<>();
                 List<List<String>> paths = new ArrayList<List<String>>();
                 List<String> path = new ArrayList<String>();
                 path.add(beginWord);
                 paths.add(path);
                 bfs(paths, wordList, endWord);
                 return ret.size();
         }
         public void bfs(List<List<String>> paths ,Set<String> wordList,String target){
                if(paths.size() == 0) {
                        return;
                }
                Iterator<List<String>> itr = paths.iterator();
                List<List<String>> pathsCopy = new ArrayList<List<String>>(paths);
                while(itr.hasNext()){
                        List<String> tempPath = itr.next();
                        pathsCopy.remove(tempPath);
                        String tempS = tempPath.get(tempPath.size()-1);
                        for (int i = 0; i < tempS.length(); i++) {
                                for (int j = 0; j < 25; j++) {
                                        char temp = (char) ('a' + j);
                                        if(tempS.charAt(i) != temp){
                                                String nString =tempS.substring(0, i) + temp + tempS.substring(i+1);
                                                if(wordList.contains(nString)) {
                                                        List<String> currPath = new ArrayList<String>(tempPath);
                                                        currPath.add(nString);
                                                        wordList.remove(nString);
                                                        if(nString.equals(target)){
                                                                ret = currPath;
                                                                return;
                                                        }
                                                        pathsCopy.add(currPath);
                                                }
                                        }
                                }
                        }
                }
                bfs(pathsCopy, wordList, target);
         }
}
 楼主| liuwujijay 发表于 2016-4-9 00:14:42 | 显示全部楼层
是不是因为 List<String> currPath = new ArrayList<String>(tempPath); 是一个O(N)的操作?
回复 支持 反对

使用道具 举报

xianming 发表于 2016-4-10 05:56:12 | 显示全部楼层
我刷这题时,当时也有个大数据总是报内存不够。我是用C++刷的,后来把参数改为by reference,加了个&,就过了。这个经验不知对楼主是否有帮助。
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-10 08:18:00 | 显示全部楼层
String的构造改成stringbuilder
回复 支持 反对

使用道具 举报

sevenyunan 发表于 2016-4-10 08:22:51 | 显示全部楼层
可以用dfs吗
回复 支持 反对

使用道具 举报

zdhzh05 发表于 2016-4-10 15:33:23 | 显示全部楼层
这题不是word ladder II,bfs不用记录每条路径(这里会浪费时间,数据量大的话还会内存溢出),每遍历一层未访问节点,层数(距离)自增,直到找到目标节点,或bfs结束(未找到目标节点)
回复 支持 反对

使用道具 举报

zdhzh05 发表于 2016-4-10 15:41:11 | 显示全部楼层

应该不行,bfs只要找到目标就可以了,但dfs要搜索每条路径,不断更新到目标的距离(能到达目标的话),才能确保找到目标的距离是最小的
回复 支持 反对

使用道具 举报

xperzy 发表于 2016-4-13 01:57:35 | 显示全部楼层
双向宽度优先应该是可以搞定的吧

我的blog里有相关:http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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