Problem Description:
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a timeEach transformed word must exist in the word list. Note that beginWord is not a transformed word.Note:
Return an empty list if there is no such transformation sequence.All words have the same length.All words contain only lowercase alphabetic characters.You may assume no duplicates in the word list.You may assume beginWord and endWord are non-empty and are not the same.Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]Example 2:
Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.Analysis:
方法一采用了深度遍历的搜索方法，但是会出现超时。
方法二采用了宽度遍历的搜索方法AC。
代码如下：
Code:
方法一（超时）：
class Solution { String endWord; int minStep = Integer.MAX_VALUE; List<List<String>> res = new ArrayList<>(); public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { for(int i = 0; i < wordList.size(); i++) { if(wordList.get(i).equals(endWord)) { break; } if(i >= wordList.size() - 1) return new ArrayList<>(); } this.endWord = endWord; wordList.add(beginWord); boolean[] isVis = new boolean[wordList.size()]; isVis[wordList.size() - 1] = true; ArrayList<String> temp = new ArrayList<>(); temp.add(beginWord); dfsHelper(wordList, wordList.size() - 1, isVis, temp); for(int i = 0; i < res.size(); i++) { if(res.get(i).size() > minStep) { res.remove(i); i--; } } return res; } public void dfsHelper(List<String> wordList, int cur, boolean[] isVis, ArrayList<String> temp) { //System.out.println(wordList.get(cur)); if(temp.size() > minStep || cur >= wordList.size()) { return; } if(wordList.get(cur).equals(this.endWord)) { //temp.add(this.endWord); ArrayList<String> ans = (ArrayList<String>)temp.clone(); minStep = Math.min(minStep, ans.size()); res.add(ans); return; } for(int i = 0; i < wordList.size(); i++) { if(isVis[i] != true && fComp(wordList.get(cur), wordList.get(i))) { isVis[i] = true; temp.add(wordList.get(i)); dfsHelper(wordList, i, isVis, temp); temp.remove(temp.size() - 1); isVis[i] = false; } } } public boolean fComp(String a, String b) { int cnt = 0; for(int i = 0; i < a.length(); i++) { if(a.charAt(i) == b.charAt(i)) { cnt++; } } if(cnt == a.length() - 1) { //System.out.println(a + ", " + b); return true; } return false; } }方法二：
class Solution { public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { HashSet<String> dict = new HashSet<>(wordList); HashMap<String, Integer> distance = new HashMap<>(); HashMap<String, List<String>> adj = new HashMap<>(); List<List<String>> result = new ArrayList<>(); List<String> path = new ArrayList<>(); dict.add(beginWord); bfs(beginWord, endWord, dict, adj, distance); path.add(beginWord); dfs(beginWord, endWord, result, path, dict, adj, distance); return result; } public List<String> getNeighbor(String word, HashSet<String> dict) { List<String> result = new ArrayList<>(); char[] arr = word.toCharArray(); for(char c = 'a'; c <= 'z'; c++) { for(int i = 0; i < arr.length; i++) { if(arr[i] == c) { continue; } char ch = arr[i]; arr[i] = c; if(dict.contains(String.valueOf(arr))) { result.add(String.valueOf(arr)); } arr[i] = ch; } } return result; } public void bfs(String start, String end, HashSet<String> dict, HashMap<String, List<String>> adj, HashMap<String, Integer> distance) { for(String word : dict) { adj.put(word, new ArrayList<String>()); } Queue<String> queue = new LinkedList<>(); queue.offer(start); distance.put(start, 0); while(!queue.isEmpty()) { String curr = queue.poll(); int level = distance.get(curr); List<String> neighbor = getNeighbor(curr, dict); for(String nei : neighbor) { adj.get(curr).add(nei); if(!distance.containsKey(nei)) { distance.put(nei, level + 1); if(!end.equals(nei)) { queue.offer(nei); } } } } } public void dfs(String curr, String end, List<List<String>> result, List<String> path, HashSet<String> dict, HashMap<String, List<String>> adj, HashMap<String, Integer> distance) { if(curr.equals(end)) { result.add(new ArrayList<>(path)); return; } for(String nei : adj.get(curr)) { path.add(nei); if(distance.containsKey(nei) && distance.get(nei) == distance.get(curr) + 1) { dfs(nei, end, result, path, dict, adj, distance); } path.remove(path.size() - 1); } } }
