127. Word Ladder
# hard
这道题不仅代码不好写，还很容易超时，前后尝试了3种方法：
DFS＋Backtracking 方法，每次换一个
wordList里的字符串走到底，记录最短路径（我觉得DFS好像和Backtracking是一回事，Backtracking思路一定要清晰）；一定要有个path记录当前路径，并且要用一个变量j记录wordList里的元素不回头检索，否则会陷入死循环。也不能检索过的元素就从wordList里删除，因为在递归里起不到作用，而且切记不要改变input的东西DFS＋Backtracking 方法，每次换一个26个字母表里的字符，然后跟
wordList里的元素对比，存在则换掉，这种方法在n很大时节约了时间；注意特例，如果wordList里有beginWord，一定要在变换的时候避免这种毫无意义的变换。但这种方法在n很大的情况下依然容易超时BFS求出最短路径，从
endWord反向推，这时顺便记录wordList里的每个元素到endWord的最短距离。如果要求最短路径，直接用BFS，如果要求出任意最短路线，直接用DFS，如果要求出所有最短路径，则需要用BFS＋DFS，参考126. Word Ladder II。BFS 求出最短路径。先预处理
wordList里的元素成一个HashMap:HashMap<String, ArrayList<String>>，wordList里的单词每减去一个字符成为key，这个单词存放在value的ArrayList里，这样需要O(word.length * wordList.size)存储空间和时间。从beginWord开始检索，beginWord任意减掉一个字符对应HashMap里的key，value 里的单词全都作为它的邻居，以此类推，直到找到endWord。BFS + hashMap, 从beginWord开始，hashMap记录从beginWord到任意wordList里的单词所需的最短路径（每次用26个字母里的一个字母替换掉旧单词的一位），即当添加新单词时，其的路径等于原单词路径+1，然后再也不更新了，这就是最短路径BFS，需要用queue记录旧单词
class Solution {
int ladder = Integer.MAX_VALUE;
List<String> path = new ArrayList<String>();
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
dfs(beginWord, endWord, wordList, 0);
if(ladder < Integer.MAX_VALUE) return ladder;
else return 0;
}
void dfs(String beginWord, String endWord, List<String> wordList, int count){
if(beginWord.compareTo(endWord) == 0){
if(count+1 < ladder) {
ladder = count+1;
for(int x = 0; x < path.size(); x++)
System.out.print(";"+ path.get(x));
}
System.out.println();
return;
}
for(int i = 0; i < beginWord.length(); i ++){
int j = 0;
while(j < wordList.size()){
StringBuilder temp = new StringBuilder();
for(int x = 0; x < beginWord.length(); x ++){
temp.append(beginWord.charAt(x));
}
j = change(temp,wordList,i,j); // i is the character in word will be changed, j is the start searching index of wordList
if(j == 0)
break;
String begin = new String(temp);
// System.out.println("begin="+ begin);
path.add(begin);
dfs(begin, endWord, wordList, count+1);
path.remove(path.size()-1);
}
}
}
int change(StringBuilder temp, List<String> wordList, int i,int j){
// System.out.println("enter change temp = "+ temp);
char ch = temp.charAt(i);
String alph = new String("abcdefghijklmnopqrstuvwxyz");
for(int x = 0; x < 26; x++){
if(ch == alph.charAt(x)) {
continue;
}
temp.setCharAt(i, alph.charAt(x));
if(wordList.contains(new String(temp)) && !path.contains(new String(temp)) && wordList.indexOf(new String(temp)) >= j){
// System.out.println("new temp="+temp);
return wordList.indexOf(new String(temp))+1;
}
}
// for(int x = j; x < wordList.size(); x ++){
// if(path.contains(wordList.get(x))) continue;
// boolean flag1 = true, flag2 = true;
// for(int y = 0; y < temp.length(); y ++){
// if(y == i && temp.charAt(i) == wordList.get(x).charAt(y)) {
// flag1 = false;
// break;
// }
// if(y != i && temp.charAt(y) != wordList.get(x).charAt(y)){
// flag2 = false;
// break;
// }
// }
// //System.out.println("worldList=" + wordList.get(x));
// if(flag1 && flag2){
// // System.out.println("enter true");
// temp.setCharAt(i, wordList.get(x).charAt(i));
// // System.out.println("intend change word to=" + wordList.get(x));
// // System.out.println("temp =" + temp);
// return x+1;
// }
// }
return 0;
}
}class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Queue<String> que = new LinkedList<String>();
int ladder = 1;
if(!wordList.contains(endWord)) return 0;
wordList.remove(endWord);
wordList.add(beginWord);
que.offer(endWord);
que.offer("#");
while(!que.isEmpty()){
String midWord = new String(que.poll());
System.out.println(midWord);
if(midWord.equals("#")){
if(!que.isEmpty()){
que.offer("#");
ladder ++;
}
continue;
}
int i = beginWord.length()-1; // ith character in midWord
while(i >= 0){
int j = -1; // jth word in wordList
while(j < wordList.size()){
j = change(wordList, midWord, i);
if(j == -1) break;
//System.out.println(j);
if(wordList.get(j).equals(beginWord)) return ladder+1;
System.out.println(wordList.get(j));
que.offer(wordList.get(j));
wordList.remove(wordList.get(j));
}
i --;
}
}
return 0;
}
int change(List<String> wordList, String midword, int i){
StringBuilder temp = new StringBuilder(midword);
String alp = "abcdefghijklmnopqrstuvwxyz";
char ch = temp.charAt(i);
for(int j = 0; j < 26; j ++){
if(alp.charAt(j) == ch) continue;
temp.setCharAt(i, alp.charAt(j));
//System.out.println(temp);
if(wordList.contains(new String(temp))){
return wordList.indexOf(new String(temp));
}
}
return -1;
}
}Solution 5, BFS + hashMap(fail to handle large input, Python and Java)
class Solution {
Map<String, List<String>> map = new HashMap<>();
Map<String, List<String>> adjList = new HashMap<>();
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(!wordList.contains(endWord))
return 0;
if(wordList.contains(beginWord)) {
wordList.remove(beginWord);
}
createMap(beginWord, wordList);
System.out.println(map);
int shortest = createAdjList(beginWord, endWord);
return shortest;
}
private void createMap(String beginWord, List<String> wordList) {
List<String> nextWord = findNext(wordList, beginWord);
map.put(beginWord, nextWord);
for(int i = 0; i < wordList.size(); i ++) {
nextWord = findNext(wordList, wordList.get(i));
map.put(wordList.get(i), nextWord);
}
}
private List<String> findNext(List<String> wordList, String word) {
String letters = "abcdefghijklmnopqrstuvwxyz";
List<String> next = new ArrayList<>();
for(int i = 0; i < word.length(); i ++) {
for(int j = 0; j < letters.length(); j ++) {
String newWord = word.substring(0, i) + letters.charAt(j) + word.substring(i+1, word.length());
if(!newWord.equals(word) && wordList.contains(newWord))
next.add(newWord);
}
}
return next;
}
private int createAdjList(String beginWord, String endWord) {
Queue<String> q = new LinkedList<String>();
q.add(beginWord);
Map<String, Integer> visited = new HashMap<String, Integer>();
int layer = 0;
while(q.size() > 0) {
int l = q.size();
layer ++;
for(int i = 0; i < l; i++) {
String currWord = q.poll();
adjList.put(currWord, new ArrayList<String>());
List<String> next = map.get(currWord);
for(String s: next) {
if(currWord.equals(endWord))
return layer;
if(visited.containsKey(s) && visited.get(s) != layer)
continue;
visited.put(s, layer);
adjList.get(currWord).add(s);
q.add(s);
}
}
}
return 0;
}
}Solution 5 的优化，去掉了hashMap，因为只需要知道一共有多少层，一个变量res足够记录了。尝试所有可能的下一个newWord，放进queue里，每一层都尝试替换单词看是否能够变成endWord. 依然处理不了大大输入. Python
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# edge case
if endWord not in wordList:
return 0
# regular case
ch = 'abcdefghijklmnopqrstuvwxyz'
queue = [beginWord]
res = 0
while len(queue) != 0:
n = len(queue)
while n > 0:
word = queue.pop(0)
if word == endWord:
return res + 1
for i in range(len(word)):
newWord = word
for j in range(len(ch)):
newWord = newWord[:i] + ch[j] + newWord[i+1:]
if newWord in wordList and newWord != word:
wordList.remove(newWord)
queue.append(newWord)
n -= 1
res += 1
return 0int, char 等基本数据类型可以直接用
＝＝比较大小，＝＝比较的是值，但String 不能直接比较，String a ＝＝ String b比较的是地址，地址当然不可能相等，可以用String1.equals(String 2)比较。String与StringBuilder是两种数据类型，如果需要用到equal或者contains或者add，都必须现转换成String 类型，例如
a.contains(new String(b))。在迭代中，千万不要修改传入的数据
在判断
BFS下一层时检查#，要判断poll出#后栈是否为空，为空不再添加#，直接退出Queue是用LinkedList接口实现，用offer()进队列，poll()出队列，若发生异常返回null。Stack是用Stack接口实现，用push()进栈，pop()出栈，若发生异常返回null。如
char[] \ int[]基础数据类型的长度，为a.length，如List的长度， 为a.size()，如String的长度，为a.length()。
Last updated
Was this helpful?