Word Ladder I & II
Last updated
Was this helpful?
Last updated
Was this helpful?
著名 gay 题，时间复杂度爆炸的典范，也是目前我知道的 leetcode 题里唯一一道非常适合使用 bi-directional bfs 的问题。
比较独特的是这题不是 DFS + Backtracking，主要原因在于我们要确保 “路线最短” ，这个更适合用 BFS 解决，两层字典首次相交的地方一定是最短路线。
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if(beginWord.length() != endWord.length()) return 0;
if(wordList == null || wordList.size() == 0) return 0;
if(beginWord.equals(endWord)) return 2;
HashSet<String> beginSet = new HashSet<String>();
HashSet<String> endSet = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
wordList.remove(beginWord);
wordList.remove(endWord);
return bfs(2, beginSet, endSet, wordList);
}
private int bfs(int steps, Set<String> beginSet, Set<String> endSet, Set<String> wordSet){
HashSet<String> nextLevel = new HashSet<String>();
for(String beginWord : beginSet){
char[] charArray = beginWord.toCharArray();
for(int pos = 0; pos < charArray.length; pos++){
for(char chr = 'a'; chr <= 'z'; chr++){
charArray[pos] = chr;
String str = String.valueOf(charArray);
if(endSet.contains(str)) return steps;
if(wordSet.contains(str)){
nextLevel.add(str);
wordSet.remove(str);
}
}
charArray = beginWord.toCharArray();
}
}
if(nextLevel.size() == 0) return 0;
if(endSet.size() < nextLevel.size()){
return bfs(steps + 1, endSet, nextLevel, wordSet);
} else {
return bfs(steps + 1, nextLevel, endSet, wordSet);
}
}
}除了递归之外，还可以用迭代。反正迭代的 BFS 好写。
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if(beginWord.length() != endWord.length()) return 0;
if(wordList == null || wordList.size() == 0) return 0;
if(beginWord.equals(endWord)) return 2;
HashSet<String> beginSet = new HashSet<String>();
HashSet<String> endSet = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
wordList.remove(beginWord);
wordList.remove(endWord);
int steps = 2;
while(!beginSet.isEmpty()){
HashSet<String> nextLevel = new HashSet<String>();
for(String word : beginSet){
char[] charArray = word.toCharArray();
for(int pos = 0; pos < charArray.length; pos++){
for(char chr = 'a'; chr <= 'z'; chr++){
charArray[pos] = chr;
String str = String.valueOf(charArray);
if(endSet.contains(str)) return steps;
if(wordList.contains(str)){
nextLevel.add(str);
wordList.remove(str);
}
}
charArray = word.toCharArray();
}
}
steps ++;
if(nextLevel.size() < endSet.size()){
beginSet = nextLevel;
} else {
beginSet = endSet;
endSet = nextLevel;
}
}
return 0;
}
}LeetCode 著名 gay 题的加强版，烦人程度更上一层楼。。。当要返回所有 path 的时候，细节处理就更多了。其实这题和 Longest Increasing Subsequence 的 follow-up ，返回所有 LIS 有相通的地方，都是维护一个 Directed Graph 关系并且从某一个终点进行 dfs 返回所有 valid path.
这题的最终解法是一个 Bi-directional BFS 与 DFS 的结合，因为 bfs 过程中起点终点会调换，为了保证 path 的正确性要 keep track of direction.
public class Solution {
boolean isConnected = false;
public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
Set<String> top = new HashSet<String>();
top.add(beginWord);
Set<String> bot = new HashSet<String>();
bot.add(endWord);
Map<String, List<String>> map = new HashMap<String, List<String>>();
// BFS 在这里只是起到一个更新 hashmap 的作用，hashmap 存着所有有效的 adjacency list
bfs(top, bot, wordList, false, map);
List<List<String>> rst = new ArrayList<List<String>>();
if(!isConnected) return rst;
List<String> list = new ArrayList<String>();
list.add(beginWord);
// DFS 负责返回并写入所有 paths
dfs(rst, list, beginWord, endWord, map);
return rst;
}
// @param swap: whether we are pointing at the right direction, start->end
// since we use bi-directional BFS it's necessary to keep track of
// directions in hashmap to construct paths
public void bfs(Set<String> top, Set<String> bot, Set<String> dict, boolean swap, Map<String, List<String>> map){
HashSet<String> nextLevel = new HashSet<String>();
// 避免搜索重复元素，免得搜索路径上出现环
dict.removeAll(top);
dict.removeAll(bot);
for(String src : top){
for(int pos = 0; pos < src.length(); pos++){
char[] array = src.toCharArray();
for(char chr = 'a'; chr <= 'z'; chr++){
if(array[pos] == chr) continue;
array[pos] = chr;
String next = String.valueOf(array);
// 决定 src 与 next 两个单词的 directed edge 方向
String key = (swap) ? next: src;
String value = (swap) ? src: next;
if(!map.containsKey(key)) map.put(key, new ArrayList<String>());
// 前面已经把先后顺序确定了，map更新就老老实实 key - value 就好
if(bot.contains(next)){
map.get(key).add(value);
isConnected = true;
}
if(dict.contains(next)){
map.get(key).add(value);
nextLevel.add(next);
}
}
}
}
if(isConnected || nextLevel.size() == 0) return;
// 这里直接扔 true / false 是不对的，应该用原来传进来的变量 swap 来决定
if(nextLevel.size() <= bot.size()){
bfs(nextLevel, bot, dict, swap, map);
} else {
bfs(bot, nextLevel, dict, !swap, map);
}
}
public void dfs(List<List<String>> rst, List<String> list, String start, String end, Map<String, List<String>> map){
if(start.equals(end)){
rst.add(new ArrayList<String>(list));
return;
}
// 没有这行会导致 null pointer exception，毕竟不是每个 word 都在 hashmap 里
// word 自己是叶节点，死胡同
if(!map.containsKey(start)) return;
for(String next : map.get(start)){
list.add(next);
dfs(rst, list, next, end, map);
list.remove(list.size() - 1);
}
}
}