Word Ladder

HardGraphs

Find the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time with each intermediate word in the dictionary.

Open problem

Constraints

1 <= word length <= 10
1 <= wordList.length <= 5000

BFS over one-letter neighbors

Time O(N * L * 26)Space O(N * L)

Treat words as graph nodes connected when they differ by one letter. BFS from beginWord, generating neighbors by trying every letter at every position, returns the shortest path length.

#include <bits/stdc++.h>
using namespace std;

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    queue<string> q;
    q.push(beginWord);
    int steps = 1;
    while (!q.empty()) {
        int sz = q.size();
        for (int s = 0; s < sz; s++) {
            string word = q.front(); q.pop();
            if (word == endWord) return steps;
            for (int i = 0; i < (int)word.size(); i++) {
                char orig = word[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    word[i] = c;
                    if (dict.count(word)) { q.push(word); dict.erase(word); }
                }
                word[i] = orig;
            }
        }
        steps++;
    }
    return 0;
}