127. Word Ladder

[jason89521]

Practice Dates

• 2024/05/20

Description

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

Solution

1. Put the beginWord into the queue.
2. Start a while loop, which should end when the queue is empty.
3. Increase the level, representing the tree's level.
4. At this point, the elements in the queue will be at the same level. Pop them out and check whether they are equal to the endWord.
5. If not equal to the endWord, push all strings from the dict that differ by only one character compared to str into the queue.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> strQueue;
        strQueue.push(beginWord);
        int level = 0;
        while (!strQueue.empty()) {
            level++;
            auto levelSize = strQueue.size();
            for (int i = 0; i < levelSize; i++) {
                auto str = strQueue.front();
                strQueue.pop();
                if (str == endWord) {
                    return level;
                }

                for (int j = 0; j < str.length(); j++){
                    auto c = str[j];
                    for (int letter = 'a'; letter <= 'z'; letter++) {
                        str[j] = letter;

                        auto it = dict.find(str);
                        if (it != dict.end()) {
                            if (str != beginWord) {
                                strQueue.push(*it);
                            }
                            dict.erase(it);
                        }
                    }
                    str[j] = c;
                }

            }
        }

        return 0;
    }
};

Performance

Time complexity: