Leetcode 127. 単語接龍解題構想及びC++実現

問題解決の考え方:
まずwordListにendWordがあるかどうかを判断し,ない場合は0を返す.
pathCountはbeginWordをあるwordに変換するのに必要な長さを格納するために使用され、動的計画でステータスを記録するマトリクスに似ています.
全体プログラムは広さ優先探索の論理である.主にキューqに注目する.whileの各サイクルは二叉樹のある層を巡ることに相当する.
第1層ではqはbeginWordという文字列のみであり、第1回目の大ループでは、beginWordを1文字変えることで得られるword集合(wordはwordListにある文字列でなければならない)を、ループごとにpathCountを更新する.
最初にnewWord==endWordに出会ったとき、一番高いレベルで終了文字列に達し、その長さが一番短いです.
 

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