leetcode 127. Word Ladder

佚名 6年前 (2019-04-12) 随笔 940人围观抢沙发百度已收录

使用bfs遍历所有的

用hash记录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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