LeetCode 题解（95）: Word Ladder II

本文主要是介绍LeetCode 题解（95）: Word Ladder II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) fromstart toend, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters

题解：

先用BFS生成由start至end的hash table。

再用DFS递归查找所有路径。

第一步的核心数据结构是HashMap<String, HashSet<String>>，表示由String可以通过改变一个字符所能转化的所有字符Set。

注意替换字符再在set中查找的优化，否则超时。

C++版：

class Solution {
public:vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {vector<vector<string>> results; if(start.length() == 0 || end.length() == 0 || dict.size() == 0)return results;dict.insert(end);dict.insert(start);unordered_map<string, unordered_set<string>> trace;for(auto i : dict) {unordered_set<string> temp;trace.insert(pair<string, unordered_set<string>>(i, temp));}unordered_set<string> q1, q2, visited;q1.insert(end);bool found = false;while(q1.size() != 0 && !found) {for(auto i : q1)visited.insert(i);for(auto current : q1) {for(int i = 0; i < current.length(); i++) {for(char j = 'a'; j <= 'z'; j++) {string temp = current;temp[i] = j;if(visited.find(temp) == visited.end() && dict.find(temp) != dict.end()) {if(temp == start)found = true;q2.insert(temp);trace[temp].insert(current);}}}}q1 = q2;q2.clear();}vector<string> result;if(found)findPaths(trace, result, results, start);return results;}void findPaths(unordered_map<string, unordered_set<string>>& trace, vector<string>& result, vector<vector<string>>& results, string& start) {vector<string> extendedResult = result;extendedResult.push_back(start);if(trace[start].size() == 0) {results.push_back(extendedResult);return;}for(auto i : trace[start]) {findPaths(trace, extendedResult, results, i);}}
};

Java版：

public class Solution {public List<List<String>> findLadders(String start, String end, Set<String> dict) {List<List<String>> results = new ArrayList<List<String>>();if(start.isEmpty() || end.isEmpty() || dict.isEmpty())return results;Set<String> q1 = new HashSet<>();Map<String, Set<String>> p = new HashMap<>();q1.add(end);dict.add(end);dict.add(start);for(String i : dict) {Set<String> temp = new HashSet<>();p.put(i, temp);}Set<String> visited = new HashSet<>();boolean found = false;while(!q1.isEmpty() && !found) {for(String i : q1)visited.add(i);Set<String> q2 = new HashSet<>();for(String current : q1) {char[] curChar = current.toCharArray();for(int i = 0; i < current.length(); i++) {char original = curChar[i];for(char j = 'a'; j <= 'z'; j++) {curChar[i] = j;String newStr = new String(curChar);if(!visited.contains(newStr) && dict.contains(newStr)) {if(newStr.equals(start))found = true;p.get(newStr).add(current);q2.add(newStr);}}curChar[i] = original;}}q1 = q2;}List<String> result = new ArrayList<>();if(found)generateResult(result, start, p, results);return results;}void generateResult(List<String> result, String start, Map<String, Set<String>> p, List<List<String>> results) {List<String> extendedResult = new ArrayList<>(result);extendedResult.add(start);if(p.get(start).size() == 0) {results.add(extendedResult);return;}for(String s : p.get(start)) generateResult(extendedResult, s, p, results);}
}

Python版：

class Solution:# @param start, a string# @param end, a string# @param dict, a set of string# @return a list of lists of stringdef findLadders(self, start, end, dict):dict.add(start)dict.add(end)results, result, q1, visited, found, d = [], [], [end], set([end]), False, {word : [] for word in dict}if len(start) == 0 or len(end) == 0 or len(dict) == 0:return resultswhile len(q1) != 0 and not found:for i in q1:visited.add(i)q2 = set([])for current in q1:for i in range(len(current)):for j in "abcdefghijklmnopqrstuvwxyz":candidate = current[0:i] + j + current[i+1:]if candidate not in visited and candidate in dict:if candidate == start:found = Trueq2.add(candidate)d[candidate].append(current)q1 = q2if found:self.findPaths(results, result, d, start)return resultsdef findPaths(self, results, result, d, start):extendedResult = copy.copy(result)extendedResult.append(start)if not d[start]:results.append(extendedResult)returnfor i in d[start]:self.findPaths(results, extendedResult, d, i)

这篇关于LeetCode 题解（95）: Word Ladder II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---