Word Ladder II
update Jul 21, 2017 21:42
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
Notice
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Example
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Basic Idea:
这道题目的难点是要求出所有最短路径。之前的 Word Ladder I 只要求输出最短路径的长度，我们只需要做一次BFS即可，但是现在要求所有的最短路径，我们就需要结合DFS。因为BFS得到的结果是一个一个分层的点，我们所能知道的只有起点到达某个状态需要几步，
具体地，我们可以先用BFS确定最短路径的长度，然后用DFS找到所有路径。我们还可以利用BFS的结果进行优化： 1. 从 end 开始做 BFS 找 start，记录沿途各点到 end 的距离，找到 start 就可以停止。 2. 将其他点与 end 的距离都标记为无穷。 3. 当我们DFS的时候，首先只选择有距离记录的相邻点开始，并且每次都只选择更近的点继续DFS，这样可以避免很多没有必要的搜索。当步数超过最短步数时则停止dfs。 4. 注意dfs出口的细节。
Java Code:
public class Solution {
/*
* @param start: a string
* @param end: a string
* @param dict: a set of string
* @return: a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> res = new ArrayList<>();
if (start.equals(end)) {
res.add(new ArrayList<>());
res.get(0).add(start);
return res;
}
dict.add(start);
dict.add(end);
Map<String, Integer> dists = new HashMap<>();
dists.put(start, Integer.MAX_VALUE);
dists.put(end, 0);
int length = getLength(start, end, dict, dists);
dfs(start, end, new HashSet<String>(), new ArrayList<String>(), res, length, dists);
return res;
}
private int getLength(String start, String end, Set<String> dict, Map<String, Integer> dists) {
int length = 1;
Deque<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offerLast(end);
while (! queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; ++k) {
String curr = queue.pollFirst();
if (! dict.contains(curr) || visited.contains(curr)) continue;
else if (curr.equals(start)) return length;
visited.add(curr);
dists.put(curr, length);
for (String neighbor : getNeighbors(curr)) {
queue.offerLast(neighbor);
}
}
length++;
}
return -1;
}
private List<String> getNeighbors(String word) {
List<String> ret = new ArrayList<>();
char[] arr = word.toCharArray();
for (int i = 0; i < arr.length; ++i) {
char t = arr[i];
for (char c = 'a'; c <= 'z'; ++c) {
arr[i] = c;
ret.add(new String(arr));
}
arr[i] = t;
}
return ret;
}
private void dfs(String start, String end, Set<String> visited, List<String> path,
List<List<String>> res, int remainSteps, Map<String, Integer> dists) {
if (remainSteps == 1) {
if (start.equals(end)) {
path.add(start);
res.add(new ArrayList<>(path));
path.remove(path.size() - 1);
}
return;
}
path.add(start);
visited.add(start);
for (String neighbor : getNeighbors(start)) {
if (visited.contains(neighbor)) continue;
if (dists.getOrDefault(neighbor, Integer.MAX_VALUE) < dists.get(start)) {
dfs(neighbor, end, visited, path, res, remainSteps - 1, dists);
}
}
visited.remove(start);
path.remove(path.size() - 1);
}
}
Python Code:
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
if start == end:
return [[start]]
dict = set(dict)
dict.add(start)
dict.add(end)
# bfs找从end到start最短路径, 并沿途记录各点距离end的路径长度
distances = {node : float('INF') for node in dict}
distances[end] = 1
minStep = self.bfs(end, start, dict, distances)
# dfs
res = []
self.dfs(start, end, dict, set(), distances, minStep, res, [])
return res
# 使用BFS找到从end到start的最短路径长度
# str start, str target, set<str> dict
def bfs(self, start, target, dict, distances):
visited = set()
queue = collections.deque()
queue.appendleft(start)
visited.add(start)
step = 1
while queue:
step += 1
size = len(queue)
for i in range(size):
node = queue.pop()
for neighbor in self.getNeighbors(node, dict, visited):
if neighbor == target: return step
visited.add(neighbor)
queue.appendleft(neighbor)
distances[neighbor] = step
# str node, set<str> dict, set<str> visited
def getNeighbors(self, node, dict, visited):
neighbors = []
for i in range(len(node)):
for c in range(ord('a'), ord('z') + 1):
neighbor = node[: i] + chr(c) + node[i + 1 :]
if neighbor in dict and neighbor not in visited:
neighbors.append(neighbor)
return neighbors
# 使用DFS找到所有长度等于最短路径的从start到end的路径
def dfs(self, start, target, dict, visited, distances, remainSteps, res, path):
# 出口
if remainSteps < 1: return
if remainSteps == 1:
if start == target:
path.append(start)
res.append(path[:])
del path[-1]
else:
return
visited.add(start)
path.append(start)
for neighbor in self.getNeighbors(start, dict, visited):
# 只选择距离end更近的点
if distances[start] <= distances[neighbor]:
continue
self.dfs(neighbor, target, dict, visited, distances, remainSteps - 1, res, path)
del path[-1]
visited.remove(start)
update 2018-05-23 18:16:44
C++ Code:
很长时间没有写比较复杂的搜索类题目，一些细节已经忘记了。
- 需要跟踪 step 数量的时候用分层 BFS 要记得加上关于 queue.size 的循环。
- 在图的DFS中，如果要获取全部路径，需要考虑到两条路径会在某一节点合并的问题，这种情况下就需要对 visited set 也进行 backtrack，保证下级dfs不会影响到上级对其他路径的搜索。
class Solution {
public:
// 主函数
vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) {
vector<vector<string>> res;
if (start == end) {
res.push_back({start});
return res;
}
dict.insert(start);
dict.insert(end);
unordered_map<string, int> dists;
dists[end] = 0;
dists[start] = 0x7fffffff;
int length = getLength(dict, dists, start, end);
vector<string> path;
unordered_set<string> visited;
dfs(dict, start, end, path, res, visited, length, dists);
return res;
}
// 获取最短路径长度，从end出发找start，并记录沿途string到end的距离
int getLength(unordered_set<string>& dict, unordered_map<string, int>& dists, string start, string end) {
unordered_set<string> visited;
deque<string> _queue;
_queue.push_back(end);
int step = 1;
while (! _queue.empty()) {
int size = _queue.size();
for (int k = 0; k < size; ++k) {
string curr = _queue.front();
_queue.pop_front();
if (! dict.count(curr) || visited.count(curr)) {
continue;
} else if (curr == start) {
cout << step << endl;
return step;
} else {
dists[curr] = step;
visited.insert(curr);
}
vector<string> neighbors = getNeighbors(curr);
for (string& neighbor : neighbors) {
_queue.push_back(neighbor);
}
}
++step;
}
return -1;
}
// 替换每个字母生成所有距离为1的string
vector<string> getNeighbors(const string& word) {
vector<string> ret;
for (int i = 0; i < word.size(); ++i) {
string neighbor = word;
for (char c = 'a'; c <= 'z'; ++c) {
neighbor[i] = c;
ret.push_back(neighbor);
}
}
return move(ret);
}
// dfs找所有路径，注意在剪枝的时候只考虑有记录距离并且到end距离小于当前点的neighbor
void dfs(unordered_set<string>& dict, string start, string end, vector<string>& path,
vector<vector<string>>& res, unordered_set<string>& visited, int remainSteps,
unordered_map<string, int>& dists) {
if (remainSteps == 1) {
if (start == end) {
path.push_back(start);
res.push_back(path);
path.pop_back();
}
return;
}
else if (visited.count(start)) return;
path.push_back(start);
visited.insert(start);
for (string neighbor : getNeighbors(start)) {
if (! dists.count(neighbor) || dists[neighbor] >= dists[start]) continue;
dfs(dict, neighbor, end, path, res, visited, remainSteps - 1, dists);
}
visited.erase(start);
path.pop_back();
}
};
update 2018-06-23 22:32:38
Update, 一些思路缕清
先进行一次 BFS，利用其结果优化DFS。首先，我们选择从 end 出发 bfs 搜索 start，并将沿途经过的 word 加入一个 set 中。当开始DFS的时候，只选择在之前 BFS 时候遇到过的 word 继续搜索。这么做的理论依据是当我们从 end 出发 dfs 找到 start 时，其经过的 vertices 一定包含了所有从start出发到end的最短路径中的节点。
update 2018-09-30 16:42:30
Update， LeetCode版本，优化
利用BFS标记每个word对应的到end的距离，如果dfs时遇到某个word对应距离和记录的不相同，就可以剪枝。用这种方法也可以直接解决去重问题，所以就不再需要visited set。
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
Set<String> dict = new HashSet<>(wordList);
Map<String, Integer> dists = new HashMap<>();
int minDist = Integer.MAX_VALUE;
dict.add(beginWord);
minDist = bfs(endWord, beginWord, dict, dists);
List<String> path = new ArrayList<>();
path.add(beginWord);
dfs(beginWord, endWord, dict, dists, minDist, path, res);
return res;
}
private void dfs(String begin, String end, Set<String> dict, Map<String, Integer> dists,
int len, List<String> path, List<List<String>> res) {
if (len < 0) return;
else if (dists.getOrDefault(begin, Integer.MAX_VALUE) != len) return;
else if (len == 0) {
if (begin.equals(end)) res.add(new ArrayList<>(path));
return;
}
List<String> neighbors = getNeighbors(begin);
for (String neighbor : neighbors) {
if (dict.contains(neighbor)) {
path.add(neighbor);
dfs(neighbor, end, dict, dists, len - 1, path, res);
path.remove(path.size() - 1);
}
}
}
private int bfs(String begin, String end, Set<String> dict, Map<String, Integer> dists) {
Deque<String> queue = new ArrayDeque<>();
queue.offerLast(begin);
int level = 0;
while (! queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
String curr = queue.pollFirst();
if (dists.containsKey(curr)) continue; // 去重
dists.put(curr, level);
if (curr.equals(end)) {
return level; // 已经找到，且之前路径上经过的点都已经加入valid set
}
List<String> neighbors = getNeighbors(curr);
for (String neighbor : neighbors) {
if (dict.contains(neighbor)) queue.offerLast(neighbor);
}
}
level++;
}
return level;
}
private List<String> getNeighbors(String word) {
List<String> ret = new ArrayList<>();
for (int i = 0; i < word.length(); ++i) {
for (char c = 'a'; c <= 'z'; ++c) {
if (c == word.charAt(i)) continue;
ret.add(word.substring(0, i) + c + word.substring(i + 1));
}
}
return ret;
}
}