127. Word Ladder
by Botao Xiao
Question:
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return 0 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: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
Thinking:
- Method1:
- 通过递归实现， 无法AC
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(wordList == null || wordList.size() == 0) return 0;
int len = wordList.size();
boolean[] used = new boolean[len];
List<Integer> result = new ArrayList<>();
change(beginWord, endWord, wordList, used, result, 1);
if(result.size() == 0) return 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < result.size(); i++)
min = Math.min(min, result.get(i));
return min;
}
public static void change(String current, String endWord, List<String> wordList, boolean[] used, List<Integer> result, int step){
if(current.equals(endWord)){
result.add(step);
}else{
int len = wordList.size();
for(int i = 0; i < len; i++){
if(used[i]) continue;
String temp = wordList.get(i);
if(valid(current, temp)){
used[i] = true;
change(temp, endWord, wordList, used, result, step + 1);
used[i] = false;
}
}
}
}
private static boolean valid(String s, String t){
int len = s.length();
int temp = 0;
for(int i = 0; i < len; i++){
if(s.charAt(i) != t.charAt(i))
temp++;
if(temp == 2) return false;
}
return true;
}
}
- Method 2
- 考虑使用BFS，仍然无法AC
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
LinkedList<String> q = new LinkedList<>();
if(!wordList.contains(endWord)) return 0;
q.add(beginWord);
int count = 0;
while(!q.isEmpty()){
count++;
for(int i = 0; i < q.size(); i++){
String current = q.poll();
if(current.equals(endWord)) return count;
char[] arr = current.toCharArray();
for(int j = 0; j < arr.length; j++){
for(char a = 'a'; a <= 'z'; a++){
char tempChar = arr[j];
if(a == tempChar) continue;
arr[j] = a;
String temp = String.valueOf(arr);
if(wordList.contains(temp)){
q.add(temp);
wordList.remove(temp);
}
arr[j] = tempChar;
}
}
}
}
return 0;
}
}
二刷
- 一刷的时候没有写出来这道题目，尝试了bfs但是无法AC。
- 二刷的时候参考了LeetCode 127. Word Ladder, 实际上这就是一道最短路径的题目。
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(beginWord == null || endWord == null) return 0; Set<String> wordSet = new HashSet<>(wordList); Set<String> visited = new HashSet<>(); visited.add(beginWord); int res = 1; while(!visited.contains(endWord)){ Set<String> temp = new HashSet<>(); for(String s : visited){ for(int i = 0; i < s.length(); i++){ char[] arr = s.toCharArray(); for(char c = 'a'; c <= 'z'; c++){ arr[i] = c; String newWord = new String(arr); if(wordSet.contains(newWord)){ temp.add(newWord); wordSet.remove(newWord); } } } } if(temp.size() == 0) return 0; res ++; visited = temp; } return res; } }
Third time:
- Method 1: DFS TLE
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { int len = beginWord.length(); int res = dfs(wordList, endWord, beginWord, len, new boolean[wordList.size()]); return (res == (Integer.MAX_VALUE >> 1)) ? 0 : res; } private int dfs(List<String> wordList, String endWord, String cur, int len, boolean[] visited){ if(cur.equals(endWord)) return 1; else{ int min = Integer.MAX_VALUE >> 1; for(int i = 0; i < wordList.size(); i++){ if(visited[i] || !isNext(cur, wordList.get(i), len)) continue; visited[i] = true; min = Math.min(min, dfs(wordList, endWord, wordList.get(i), len, visited) + 1); visited[i] = false; } return min; } } private boolean isNext(String pre, String next, int len){ int count = 0; for(int i = 0; i < len; i++){ if(next.charAt(i) == pre.charAt(i)) continue; else count++; if(count > 1) return false; } return count == 1; } } - Method 2: BFS AC
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> remain = new HashSet<>(wordList); LinkedList<String> queue = new LinkedList<>(); if(!remain.contains(endWord)) return 0; queue.add(beginWord); int res = 0, len = beginWord.length(); while(!queue.isEmpty()){ res++; int size = queue.size(); for(int i = 0; i < size; i++){ String cur = queue.poll(); if(cur.equals(endWord)) return res; char[] arr = cur.toCharArray(); for(int l = 0; l < len; l++){ char origin = arr[l]; for(char c = 'a'; c <= 'z'; c++){ if(c == origin) continue; arr[l] = c; String next = new String(arr); if(remain.contains(next)){ remain.remove(next); queue.add(next); } } arr[l] = origin; } } } return 0; } } - Method 3: Bidirectional bfs
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet<>(wordList); if(!dict.contains(endWord)) return 0; Set<String> head = new HashSet<>(); Set<String> tail = new HashSet<>(); head.add(beginWord); tail.add(endWord); int step = 0, len = endWord.length(); while(!head.isEmpty() && !tail.isEmpty()){ ++step; int headSize = head.size(), tailSize = tail.size(); Set<String> temp = null; if(headSize > tailSize){ temp = head; head = tail; tail = temp; } Set<String> next = new HashSet<>(); for(String s: head){ char[] arr = s.toCharArray(); for(int i = 0; i < len; i++){ for(char c = 'a'; c <= 'z'; c++){ arr[i] = c; String newWord = new String(arr); if(tail.contains(newWord)) return step + 1; if(dict.contains(newWord)){ next.add(newWord); dict.remove(newWord); } } arr[i] = s.charAt(i); } } head = next; } return 0; } }
Amazon session
- Method 1:
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet(); for(String s : wordList) dict.add(s); if(!dict.contains(endWord)) return 0; Queue<String> q = new LinkedList<>(); q.offer(beginWord); Set<String> visit = new HashSet<>(); int step = 0; int len = beginWord.length(); while(!q.isEmpty()){ int size = q.size(); step++; for(int p = 0; p < size; p++){ String cur = q.poll(); if(cur.equals(endWord)) return step; char[] arr = cur.toCharArray(); for(int i = 0; i < len; i++){ char origin = arr[i]; for(char c = 'a'; c <= 'z'; c++){ if(c == origin) continue; arr[i] = c; String next = new String(arr); if(!visit.contains(next) && dict.contains(next)){ q.offer(next); visit.add(next); } } arr[i] = origin; } } } return 0; } } - Method 2: Bi-Directional bfs
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet<>(wordList); if(!dict.contains(endWord)) return 0; Set<String> first = new HashSet<>(); first.add(beginWord); Set<String> second = new HashSet<>(); second.add(endWord); dict.remove(beginWord); dict.remove(endWord); int len = beginWord.length(); int step = 0; while(!first.isEmpty() && !second.isEmpty()){ if(first.size() > second.size()){ Set<String> temp = first; first = second; second = temp; } step++; Set<String> next = new HashSet<>(); for(String cur: first){ char[] arr = cur.toCharArray(); for(int i = 0; i < len; i++){ char origin = arr[i]; for(char c = 'a'; c <= 'z'; c++){ if(origin == c) continue; arr[i] = c; String nextStr = new String(arr); if(second.contains(nextStr)) return step + 1; if(dict.contains(nextStr)){ next.add(nextStr); dict.remove(nextStr); } } arr[i] = origin; } } first = next; } return 0; } }
Conclusion
- How to choose dfs and bfs
- bfs is designed for shortest path question.
- At one single stage, we could get the next stage and in every single step, the result is optimized, we can use bfs.
- dfs can also solve bfs questions while it takes longer time.
- dfs is used for recording all possible solutions(combination and permutation questions).
Reference
Subscribe via RSS