Word Ladder I — 只需要找一条最短路
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Example
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog"
,
return its length 5
.
Note
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Solution: BFS – BFS模板 O(n*L) n: size of dict, L: the max length of the words
visited set记录已经访问过的路 一旦找到一条就退出
注意字符串的处理
public int ladderLength(String start, String end, Set<String> dict) { if (dict == null || dict.size() == 0) { return 0; } Queue<String> queue = new LinkedList<String>(); queue.offer(start); int length = 1; Set<String> visited = new HashSet<>(); visited.add(start); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String curr = queue.poll(); for (char newChar = 'a'; newChar <= 'z'; newChar++) { for (int j = 0; j < start.length(); j++) { if (newChar == curr.charAt(j)) { continue; } String nextStep = curr.substring(0, j) + newChar + curr.substring(j + 1); if (nextStep.equals(end)) { return length + 1; } if (dict.contains(nextStep) && !visited.contains(nextStep)) { queue.offer(nextStep); visited.add(nextStep); } } } } length++; } return 0; }
Word Ladder II –找出所有最短路
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Solution: BFS+DFS
1. 先用BFS找出最短路径的长度,同时把相邻节点和每个点到起点的distance保存下来
2. 用DFS找出所有最短路径,distance超过最短路径的长度的就不用考虑了,所谓pruning.
public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> result = new ArrayList<>(); if (dict == null || dict.size() == 0) { return result; } List<String> curr = new ArrayList<>(); curr.add(start); Map<String, Integer> distance = new HashMap<>(); Map<String, List<String>> neighborsMap = new HashMap<>(); int minTrans = bfs(start, end, dict, distance, neighborsMap); findLaddersHelper(curr, end, minTrans, distance, neighborsMap, result); return result; } public void findLaddersHelper(List<String> curr, String end, int maxStep, Map<String, Integer> distance, Map<String, List<String>> neighborsMap, List<List<String>> result) { String currStr = curr.get(curr.size() - 1); if (maxStep == 0) { if (currStr.equals(end)) { result.add(new ArrayList<>(curr)); } return; } for (String neighbor : neighborsMap.get(currStr)) { if (distance.get(neighbor) == distance.get(currStr) + 1) { curr.add(neighbor); findLaddersHelper(curr, end, maxStep - 1, distance, neighborsMap, result); curr.remove(curr.size() - 1); } } } //first use BFS to find the shortest transformation public int bfs(String start, String end, Set<String> dict, Map<String, Integer> distance, Map<String, List<String>> neighborsMap) { Queue<String> queue = new LinkedList<>(); queue.offer(start); distance.put(start, 0); int minTrans = -1; while (!queue.isEmpty()) { int size = queue.size(); String str = queue.poll(); List<String> neighbors = new ArrayList<>(); for (char newChar = 'a'; newChar <= 'z'; newChar++) { for (int index = 0; index < start.length(); index++) { if (newChar == str.charAt(index)) { continue; } String newStr = str.substring(0, index) + newChar + str.substring(index + 1); if (newStr.equals(end) && minTrans == -1) { minTrans = distance.get(str) + 1; } if (dict.contains(newStr)) { neighbors.add(newStr); if (!distance.containsKey(newStr)) { distance.put(newStr, distance.get(str) + 1); queue.offer(newStr); } } } } neighborsMap.put(str, neighbors); } return minTrans; }