[leetcode]Word Ladder II

这是条难题（base on time and memory limit) 大概思路就是记录每个字的parents.. 还有用hashset来装next level这样可以避免重复 当整个next level都生成完毕之后...就可以把notVisited里面的next level word 去掉 一举两得..既可以避免重复visit又可以满足同一个word有multiple parents的情况... **有个地方就是注意同样字母的时候 不应该算进possible

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

public class Solution { List<List<String>> result = new ArrayList<List<String>>(); public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { HashMap<String, List<String>> parents = new HashMap<String, List<String>>(); HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); while (!found && !curLevel.isEmpty()){ for (String cur:curLevel){ getNextWords(parents, nextLevel, notVisited, cur); } for (String next:nextLevel){ notVisited.remove(next); } if (nextLevel.contains(endWord)) found = true; HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } if (!parents.containsKey(endWord)) return new ArrayList<List<String>>(); generateResult(parents, beginWord, endWord, new LinkedList<String>()); return result; } public void generateResult(HashMap<String, List<String>> parents, String start, String end, List<String> fromPrev){ if (start == end){ LinkedList<String> temp = new LinkedList<String>(fromPrev); temp.addFirst(start); result.add(temp); return; } List<String> parent = parents.get(end); ((LinkedList<String>) fromPrev).addFirst(end); for (String upper:parent){ generateResult(parents, start, upper, fromPrev); } ((LinkedList<String>) fromPrev).removeFirst(); } public void getNextWords(HashMap<String, List<String>> parents, HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)) { nextWord.add(temp); List<String> parent = parents.containsKey(temp)?parents.get(temp):new ArrayList<String>(); parent.add(current); parents.put(temp, parent); } } } possible[i] = origin; } } }