登录
  • #刷题
  • #leetcode

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

liuwujijay
1786
7
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);

}

}
7条回复
热度排序

发表回复