C++: Word Ladder

Thought Process

The solution uses Breadth-First Search (BFS) to find the shortest transformation sequence. We start from the beginWord and explore all possible one-letter transformations at each level. Each transformation is checked against the word dictionary and marked as visited to avoid cycles. The key optimization is processing words level by level, which guarantees the shortest path is found first. Furthermore, we maintain a counter to track the number of transformations required to reach the target word, which will become our final answer. 

class Solution {
public:
    int ladderLength(string beginWord, string endWord,vector<string>& wordList) {

        set<string> dictionary(wordList.begin(), wordList.end());
        set<string> visited;
        queue<string> qu;
        int noOfchanges = 1;

        qu.push(beginWord);
        visited.insert(beginWord);

        // If dictionary doesn't contains the endWord
        if (!dictionary.contains(endWord))
            return 0;

        while (!qu.empty()) {

            int sz = qu.size();
            for (int i = 0; i < sz; i++) {

                string str = qu.front();    qu.pop();
                
                if (str == endWord)
                    return noOfchanges;

                // Take one string from the queue & do all possible unit transformations.
                for (int j = 0; j < str.size(); j++) {

                    char ref = str[j];
                    for (char ch = 'a'; ch <= 'z'; ch++) {

                        str[j] = ch;
                        if (dictionary.contains(str) && !visited.contains(str)) {
                            qu.push(str);
                            visited.insert(str);
                        }
                    }
                    str[j] = ref;
                }
            }
            noOfchanges++;
        }
        return 0; // When no such sequence exists
    }
};

Code Complexity

Time Complexity: O(M2×N)

Where 'M' is word length and 'N' is dictionary size. For each word, we check 'M' characters and 26 possible transformations.

Space Complexity: O(N)

We store the dictionary and visited words, both requiring space proportional to the number of words.

Code copied!