127. Word Ladder

BFS, vector, set

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不相同也不是空的

2.想法

• 提問

  • 確認題意:

• function header, parameter

• test input

• 觀察

  • 其實可以連成一棵樹, root為beginWord, 後一層為前一層的改變一個字母

  • 因此可以用BFS:

    • 將位於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