---
description: BFS, vector, set
---

# 127. Word Ladder

## 1.問題

* 給予兩個字 (_beginWord_ and _endWord_), 還有一個dictionary's word list, 找&#x51FA;_&#x62;eginWord_ &#x5230;_&#x65;ndWord_**最短的串列**長度
  * 這個字到下個字只能改變一個character
  * 串列中的每個字必須皆位於dictionary's word list中, _beginWord不屬&#x65BC;_&#x64;ictionary's word list
* Note:
  * 如果串列不存在則回傳0
  * dictionary's word list中的每個字具有相同長度
  * dictionary's word list中的每個字都是小寫
  * dictionary's word list中的字都不重複
  * _beginWord_ &#x53CA;_&#x65;ndWord不相同也不是空的_

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LGsGKK7q_ctBQoBTJ_3%2F-LGsJnzKSoEsJXAkf1M1%2F2018070802.jpg?alt=media\&token=bc58aacf-e838-42ec-881d-da57df1d6dfc)

## 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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LGsGKK7q_ctBQoBTJ_3%2F-LGsJUqu9JzHmtud-CDB%2F20180708.jpg?alt=media\&token=02a88094-b91c-4815-ac94-d62441984d85)
