> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/120.word-ladder.md).

# 127.Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

### Notice

* Return 0 if there is no such transformation sequence.
* 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"]`

As one shortest transformation is`"hit" -> "hot" -> "dot" -> "dog" -> "cog"`,\
return its length`5`.

**Another Version (Leetcode) :** 

A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

* Every adjacent pair of words differs by a single letter.
* Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
* `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return *the **number of words** in the **shortest transformation sequence** from* `beginWord` *to* `endWord`*, or* `0` *if no such sequence exists.*

&#x20;

**Example 1:**

```
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
```

**Example 2:**

```
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
```

&#x20;

**Constraints:**

* `1 <= beginWord.length <= 10`
* `endWord.length == beginWord.length`
* `1 <= wordList.length <= 5000`
* `wordList[i].length == beginWord.length`
* `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
* `beginWord != endWord`
* All the words in `wordList` are **unique**.

## 2.Code

<http://www.jiuzhang.com/solutions/word-ladder/>

如何转化？

1. 将每个单词看成图的一个节点。
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。
3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

无论是求最短路径长度还是求所有最短路径，都是用BFS。在BFS中有三个关键步骤需要实现:

1.如何找到与当前节点相邻的所有节点。这里可以有两个策略：

(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n\*w，n为字典中的单词数量，w为单词长度。

(2) 遍历当前单词的每个字符x，将其改变成a\~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26\*w，w为单词长度。

这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说，长度大多小于100，而字典中的单词数则往往是成千上万，所以策略2相对较优。

2.如何标记一个节点已经被访问过，以避免重复访问。可以将访问过的单词从字典中删除。

3.一旦BFS找到目标单词，如何backtracking找回路径？

caution:在替换String的某一位的字符时，先转换成char数组再操作；

```
 public static int ladderLength(String start, String end, Set<String> dict) {
       if(dict==null){
           return 0;
       }
       //这个不能忘记
       if(start.equals(end)){
           return 1;
       }

       dict.add(start);
       dict.add(end);
       //create the graph（这个可以不要，在下面直接用neighbor函数取他的下一层即可）
       HashMap<String,HashSet<String>> graph=new HashMap<>();
       for(String word: dict){
           HashSet<String> list=new HashSet<String>();
           list=neighbor(word,dict);
           graph.put(word,list);
       }

       Queue<String> queue=new LinkedList<String>();
       queue.offer(start);
       HashSet<String> visited=new HashSet<String>();
       visited.add(start);
       int length=1;
       while(!queue.isEmpty()){

           int size=queue.size();
           for(int i=0;i<size;i++){
               String current=queue.poll();
               if(current.equals(end)){
                   return length;
               }
               for(String element: neighbor(current,dict)){
                   if(!visited.contains(element)){                                
                       queue.offer(element);
                       visited.add(element);
                   }
               }
           }
           length++;
       }
       return 0;      
}       


   public static HashSet<String> neighbor(String start,Set<String> dict){
       HashSet<String> result=new HashSet<>();
       int size=start.length();
       for(int i=0;i<size;i++){
           char c=start.charAt(i);
           for(char j='a';j<='z';j++){
               if(c==j) continue;
               //这里用replace函数就错了，要用下面的方法替换
               //String neighbor=start.replace(start.charAt(i), j);
               char[] str=start.toCharArray();
               str[i]=j;
               //注意这里不能用toString(),要用new String(); reason: https://stackoverflow.com/questions/18625170/java-char-tostring
               String neighbor=new String(str);
               if(dict.contains(neighbor)){
                   result.add(neighbor);
               }
           }
       }
       return result;
   }
```

**Version of LeetCode:**

this version if the endWord is not in the dict, then it can't reach to that.

```
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        if(beginWord.length() != endWord.length()) return 0;
        if(beginWord.equals(endWord)) return 1;
        
        Set<String> set = new HashSet<>();
        for(int i = 0; i< wordList.size(); i++)
        {
            set.add(wordList.get(i));
        }
        // 注意这里跟上一个版本的不同
        if(!set.contains(endWord)) return 0;
        
        int step = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        
        Set<String> visited = new HashSet<String>();
        visited.add(beginWord);
        
        while(!queue.isEmpty())
        {
            int size = queue.size();
            for(int i = 0; i< size; i++)
            {
                String current = queue.poll();
                if(current.equals(endWord)) return step;
                List<String> neighbours = getAllAdjacents(current, set);
                for(String neighbour : neighbours)
                {
                    if(!visited.contains(neighbour))
                    {
                        queue.offer(neighbour);
                        visited.add(neighbour);
                    }
                }
            }
            step++;
        }
        // 最后是没在中间return 那么就是return 0
        return 0;   
    }
    
    public List<String> getAllAdjacents(String word, Set<String> set)
    {
        List<String> result = new ArrayList<String>();
        for(int i = 0; i< word.length(); i++)
        {
            char current = word.charAt(i);
            for(char j = 'a'; j<= 'z'; j++)
            {
                if(current == j) continue;
                char[] wordArray = word.toCharArray();
                wordArray[i] = j;
                String neighbor = new String(wordArray);
                //String neighbor = wordArray.toString();
                if(set.contains(neighbor))
                {
                    result.add(neighbor);
                }
            }
        }
        return result;
    }
}
```