Word Ladder

[mrenemy999-os]

Discussion Type

Question

Discussion Content

Transform beginWord → endWord with minimum steps.

[vivek02122003-dot]

class Solution {
public:
int ladderLength(string beginWord, string endWord, vector& wordList) {
unordered_set st(wordList.begin(), wordList.end());
if (!st.count(endWord)) return 0;

    queue<pair<string,int>> q;
    q.push({beginWord, 1});

    while (!q.empty()) {
        auto [word, steps] = q.front();
        q.pop();

        for (int i = 0; i < word.size(); i++) {
            string temp = word;
            for (char ch = 'a'; ch <= 'z'; ch++) {
                temp[i] = ch;

                if (st.count(temp)) {
                    q.push({temp, steps + 1});
                    st.erase(temp); // mark visited
                }
            }
        }
    }
    return 0;
}

};

[vivek02122003-dot]

this optimal solution

[m-khujnare2005]

Use BFS to find the shortest transformation from beginWord to endWord. At each step, change one character (a–z) and check if the new word exists in the word list. Store words in an unordered set for fast lookup and remove them once visited to avoid repetition. As soon as you reach the endWord, return the number of steps. If no transformation is possible, return 0.