Word Ladder - LeetCode

佚名 5年前 (2019-04-07) 随笔 1873人围观抢沙发百度已收录

题目链接

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

注意点

每一个变化的字母都要在wordList中

解法

解法一：bfs。类似走迷宫，有26个方向（即26个字母），起点是beginWord，终点是endWord。每一次清空完队列ret+1表示走了一步。bfs可以保证是最短路径。

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