class Solution {
public:
    int result = INT_MAX;
    int tmp_result = 1;
    int cheak(string s1 , string s2)
    {
        int no_same_num = 0;
        for(int i=0 ; i<s1.size() ;i++)
        {
            if(s1[i] != s2[i]) no_same_num++;
        }
        return no_same_num;
    }
    void track_back(string beginWord, string endWord, vector<string>& wordList , int indix, vector<bool> &path)
    {
        for(int i=0 ; i<wordList.size() ;i++)
        {
           if(wordList[indix] == endWord && path[i] == false)
            {
                if(tmp_result < result) result = tmp_result;
                // cout<<endl;
                return;
            }else if(cheak(wordList[indix],wordList[i]) == 1 && path[i] == false)
            {
                // cout<<wordList[i]<<' ';
                tmp_result ++;
                path[i] = true;
                track_back(beginWord,endWord,wordList,i,path);
                path[i] = false;
                tmp_result--;
            }
        }
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<bool> path(wordList.size(),false);
        for(int i=0 ; i<wordList.size() ;i++)
        {
            if(cheak(beginWord,wordList[i]) == 1 && path[i]==false)
            {
                // cout<<wordList[i]<<' ';
                path[i] = true;
                tmp_result++;
                track_back(beginWord,endWord,wordList,i,path);
                tmp_result--;
                path[i] = false;
            }
        }
        if(result == INT_MAX) return 0;
        return result;
    }
};

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 将vector转成unordered_set，提高查询速度
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        // 如果endWord没有在wordSet出现，直接返回0
        if (wordSet.find(endWord) == wordSet.end()) return 0;
        // 记录word是否访问过
        unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>
        // 初始化队列
        queue<string> que;
        que.push(beginWord);
        // 初始化visitMap
        visitMap.insert(pair<string, int>(beginWord, 1));
        while(!que.empty()) 
        {
            string word = que.front();
            que.pop();
            int path = visitMap[word]; // 这个word的路径长度
            for (int i = 0; i < word.size(); i++)
            {
                string newWord = word; // 用一个新单词替换word，因为每次置换一个字母
                for (int j = 0 ; j < 26; j++) 
                {
                    newWord[i] = j + 'a';
                    if (newWord == endWord) return path + 1; // 找到了end，返回path+1
                    // wordSet出现了newWord，并且newWord没有被访问过
                    if (wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()) 
                    {
                        // 添加访问信息
                        visitMap.insert(pair<string, int>(newWord, path + 1));
                        que.push(newWord);
                    }
                }
            }
        }
        return 0;
    }
};