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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/3.breadth-first-search/120.word-ladder.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.