美文网首页
6.Word Ladder

6.Word Ladder

作者: Anaven | 来源:发表于2017-01-02 12:19 被阅读0次

https://leetcode.com/problems/word-ladder/

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        if (beginWord == endWord) {
            return 1;
        }
        
        int count = 2;
        int ws = beginWord.length();
        queue<string> q;
        q.push(beginWord);
        wordList.erase(beginWord);
        
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                string word = q.front();
                q.pop();
                for (int ci = 0; ci < ws; ci++) {
                    char och = word[ci];
                    for (char nch = 'a'; nch <= 'z'; nch++) {
                        word[ci] = nch;
                        if (word == endWord) {
                            return count;
                        }
                        if (wordList.find(word) != wordList.end()) {
                            q.push(word);
                            wordList.erase(word);
                        }
                    }
                    word[ci] = och;
                }
            }
            count++;
        }
        
        return 0;
    }
};

相关文章

网友评论

      本文标题:6.Word Ladder

      本文链接:https://www.haomeiwen.com/subject/giswvttx.html