127. Word Ladder

# hard

Key idea: BFS find the shortest path

核心：BFS 找出最短路径

这道题不仅代码不好写，还很容易超时，前后尝试了3种方法：

1. DFS＋Backtracking 方法，每次换一个wordList里的字符串走到底，记录最短路径（我觉得DFS好像和Backtracking是一回事，Backtracking思路一定要清晰）；一定要有个path记录当前路径，并且要用一个变量j记录wordList里的元素不回头检索，否则会陷入死循环。也不能检索过的元素就从wordList里删除，因为在递归里起不到作用，而且切记不要改变input的东西

2. DFS＋Backtracking 方法，每次换一个26个字母表里的字符，然后跟wordList里的元素对比，存在则换掉，这种方法在n很大时节约了时间；注意特例，如果wordList里有beginWord，一定要在变换的时候避免这种毫无意义的变换。但这种方法在n很大的情况下依然容易超时

3. BFS求出最短路径，从endWord反向推，这时顺便记录wordList里的每个元素到endWord的最短距离。如果要求最短路径，直接用BFS，如果要求出任意最短路线，直接用DFS，如果要求出所有最短路径，则需要用BFS＋DFS，参考126. Word Ladder II。

4. BFS 求出最短路径。先预处理wordList里的元素成一个HashMap: HashMap<String, ArrayList<String>>，wordList里的单词每减去一个字符成为key，这个单词存放在value的ArrayList里，这样需要O(word.length * wordList.size) 存储空间和时间。从beginWord开始检索，beginWord任意减掉一个字符对应HashMap里的key，value 里的单词全都作为它的邻居，以此类推，直到找到endWord。

5. BFS + hashMap, 从beginWord开始，hashMap记录从beginWord到任意wordList里的单词所需的最短路径（每次用26个字母里的一个字母替换掉旧单词的一位），即当添加新单词时，其的路径等于原单词路径+1，然后再也不更新了，这就是最短路径BFS，需要用queue记录旧单词

Solution 1 & 2 (fail to handle big N)

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;
    }
}

Solution 3(fail to handle big N but is better than solution 1 & 2)

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)

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;
    }
}

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'        
        pathCnt = {beginWord: 1}
        queue = [beginWord]
        
        while len(queue) != 0:
            word = queue.pop(0)
            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 == endWord:
                        return pathCnt[word]+1
                    if newWord in wordList and newWord not in pathCnt:
                        pathCnt[newWord] = pathCnt[word] + 1
                        queue.append(newWord)
                        
        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 0

Chinese

学习贴士：

• int, 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()。

English