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


---

# Agent Instructions: 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://jenhsuan.gitbook.io/algorithm/leetcode/127.-word-ladder-medium.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.