> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/127.-word-ladder-medium.md).

# 127. Word Ladder

## 1.問題

* 給予兩個字 (*beginWord* and *endWord*), 還有一個dictionary's word list, 找出*beginWord* 到*endWord***最短的串列**長度
  * 這個字到下個字只能改變一個character
  * 串列中的每個字必須皆位於dictionary's word list中, *beginWord不屬於*dictionary's word list
* Note:
  * 如果串列不存在則回傳0
  * dictionary's word list中的每個字具有相同長度
  * dictionary's word list中的每個字都是小寫
  * dictionary's word list中的字都不重複
  * *beginWord* 及*endWord不相同也不是空的*

![](/files/-LGsJnzKSoEsJXAkf1M1)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意: &#x20;
* function header, parameter
* test input
* 觀察
  * 其實可以連成一棵樹, root為beginWord, 後一層為前一層的改變一個字母
  * 因此可以用BFS:&#x20;
    * 將位於wordList中, 又與該層node差異僅一個字母的字串放進queue中, 如果暫時字串位於List中, 讓cnt+1, 同時比較與暫時字串與目標字串
* 說明想法
  * 快速搜尋一字串是否在list中的方法: 將vector放到set中, 如果set.count(word)==0表示不存在
* 測試計算複雜度

## 3.程式碼

```
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> cnt;
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        queue<string> q;
        q.push(beginWord);
        cnt[beginWord] = 1;
        
        while (!q.empty()) {
            string word = q.front();
            q.pop();
            
            for (int i = 0; i < word.size(); i++) {
                string newWord = word;
                for (char tmp = 'a'; tmp <= 'z'; ++tmp) {
                    newWord[i] = tmp;
                    
                    if (wordSet.count(newWord) && newWord == endWord) {
                        return cnt[word] + 1;
                    }
                    
                    if (wordSet.count(newWord) && !cnt[newWord]) {
                        cnt[newWord] = cnt[word] + 1;
                        q.push(newWord);
                    }
                }
            }
        }
        
        return 0;
        
    }
};
```

## 4.Performance

![](/files/-LGsJUqu9JzHmtud-CDB)