Word Ladder BFS总是过不了大数据是为何？求指点！

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);
         }
}

是不是因为 List<String> currPath = new ArrayList<String>(tempPath); 是一个O(N)的操作？

我刷这题时，当时也有个大数据总是报内存不够。我是用C++刷的，后来把参数改为by reference，加了个&，就过了。这个经验不知对楼主是否有帮助。

String的构造改成stringbuilder

可以用dfs吗

这题不是word ladder II，bfs不用记录每条路径（这里会浪费时间，数据量大的话还会内存溢出），每遍历一层未访问节点，层数（距离）自增，直到找到目标节点，或bfs结束（未找到目标节点）

sevenyunan 发表于 2016-4-10 08:22
可以用dfs吗

应该不行，bfs只要找到目标就可以了，但dfs要搜索每条路径，不断更新到目标的距离（能到达目标的话），才能确保找到目标的距离是最小的

双向宽度优先应该是可以搞定的吧

我的blog里有相关：http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html