LeetCode Solutions
    Word Ladder Problems

    Word Ladder Problems

    Problem 1: Minimum Transformation Steps

    Given a start word, end word, and word list, find the minimum number of transformations where each step changes only one letter and intermediate words must exist in the dictionary.

    Core Approach

    1. Build an adjacency table based on the definition, then perform BFS to find the end word or return results after search ends.

    Time complexity: N² + N
    Space complexity: N²

    class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        map<string, vector<string> > g;
        construct_graph(beginWord, wordList, g);
        return BFS(beginWord, endWord, g);
    }
    
    // BFS
    int BFS(string &beginWord, string &endWord,
           map<string, vector<string> >& graph) {
        queue<pair<string, int> > Q;
        unordered_set<string> visit;
        Q.push(make_pair(beginWord, 1));
        visit.insert(beginWord);
        while(!Q.empty()) {
            string node = Q.front().first;
            int step=Q.front().second;
            Q.pop();
            if (node == endWord) return step;
            const vector<string> &neighbors = graph[node];
            for(int i=0;i<neighbors.size();++i) {
                // Continue searching unvisited nodes
                if (visit.find(neighbors[i])==visit.end()) {
                    Q.push(make_pair(neighbors[i], step+1));
                    visit.insert(neighbors[i]);
                }
            }
        }
        return 0;
    }
    
    // Build adjacency table using map+vector
    void construct_graph(string &beginWord,
                        vector<string>& wordList,
                        map<string, vector<string> >& graph) {
        wordList.push_back(beginWord);
        for(int i=0;i<wordList.size();++i) {
            graph[wordList[i]] = vector<string>();
        }
        for(int i=0;i<wordList.size();++i) {
            for(int j=i+1;j<wordList.size();++j) {
                if (connect(wordList[i], wordList[j])) {
                    // i connects to j bidirectionally
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
        }
    }
    
    // Check if adjacent nodes (only one different letter)
    bool connect(const string& word1, const string& word2) {
        int cnt=0;
        for(int i=0;i<word1.size()&&cnt<2;++i)
            if (word1[i]!=word2[i]) ++cnt;
        return cnt==1;
    }
};
    1. Bidirectional BFS. Change each letter of each word in sequence. This dramatically reduces the number of words to check per level. Always explore the smaller queue first.
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (dict.find(endWord)==dict.end()) return 0;

    int step=0;
    // Use set for bidirectional BFS to improve lookup efficiency
    unordered_set<string> q1{beginWord};
    unordered_set<string> q2{endWord};
    unordered_set<string> tmp;
    while(!q1.empty() && !q2.empty()) {
        ++step;
        if (q1.size()>q2.size()) swap(q1, q2);
        tmp.clear();
        for(string w : q1) {
            for(int i=0;i<w.size();++i) {
                char oldc=w[i];
                for(int j='a';j<='z';++j) {
                    w[i]=j;
                    // Bidirectional search meets, end search
                    if (q2.find(w)!=q2.end()) return step+1;
                    // Already visited
                    if (dict.find(w)==dict.end()) continue;
                    // Add to visit container, remove from word list
                    tmp.insert(w);
                    dict.erase(w);
                }
                w[i]=oldc;
            }
        }
        swap(tmp, q1);
    }

    return 0;
}

    Similar Problem

    Problem 2: Same minimum transformation search, but return all shortest transformation paths.

    Challenge Analysis

    The problem becomes: how do we record all shortest BFS paths?

    1. Normal BFS queues add target nodes to be searched next. After current nodes leave the queue, they’re not recorded. We need to modify the existing queue.

    Modification approach: Use vector to simulate queue. Each element stores the index of the previous element plus current element’s step count and content, similar to static linked list. Add to queue when minimum steps are found.

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        if (wordList.size()==0) return res;
        map<string, vector<string> > g;
        construct_graph(beginWord, wordList, g);
        vector<Qitem> Q;
        vector<int> end_pos;
        BFS(beginWord, endWord, g, Q, end_pos);
        for(int i=0;i<end_pos.size();++i) {
            int pos = end_pos[i];
            vector<string> path;
            while(pos!=-1) {
                path.push_back(Q[pos].node);
                pos=Q[pos].parent_pos;
            }
            res.push_back(vector<string>());
            for(int j=path.size()-1;j>=0;--j) res[res.size()-1].push_back(path[j]); 
        }
        return res;
    }
    
    struct Qitem {
        string node;
        int parent_pos;
        int step;
        Qitem(string _node, int _parent_pos, int _step) : node(_node), parent_pos(_parent_pos), step(_step) {}
    };
    
    void BFS(string &beginWord, string &endWord,
            map<string, vector<string> > &graph,
            vector<Qitem> &Q,
            vector<int> &end_word_pos) {
        map<string, int> visit;
        int min_step=0;
        Q.push_back(Qitem(beginWord.c_str(), -1, 1));
        visit[beginWord]=1;
        int front=0;
        while(front!=Q.size()) {
            const string &node = Q[front].node;
            int step=Q[front].step;
            if (min_step != 0 && step>min_step) break;
            if (node==endWord) {
                min_step=step;
                end_word_pos.push_back(front);
            }
            const vector<string> &neighbors = graph[node];
            for(int i=0;i<neighbors.size();++i) {
                if (visit.find(neighbors[i])==visit.end() || visit[neighbors[i]]==step+1) {
                    Q.push_back(Qitem(neighbors[i], front, step+1));
                    visit[neighbors[i]]=step+1;
                }
            }
            ++front;
        }
        
    }
    
    void construct_graph(string &beginWord,
                        vector<string>& wordList,
                        map<string, vector<string> >& graph) {
        bool hasBeginWord = false;
        for(int i=0;i<wordList.size();++i) {
            if (wordList[i]==beginWord) hasBeginWord=true;
            graph[wordList[i]] = vector<string>();
        }
        for(int i=0;i<wordList.size();++i) {
            for(int j=i+1;j<wordList.size();++j) {
                if (connect(wordList[i], wordList[j])) {
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
            if (!hasBeginWord && connect(beginWord, wordList[i]))
                graph[beginWord].push_back(wordList[i]);
        }
    }
    
    bool connect(const string& word1, const string& word2) {
        int cnt=0;
        for(int i=0;i<word1.size();++i)
            if (word1[i]!=word2[i]) ++cnt;
        return cnt==1;
    }
};

    This solution builds the graph in advance and uses vector to simulate a more complex queue, wasting space.

    1. Use map to build shortest path graph, then use DFS to find all paths.

    Unidirectional BFS:

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord)==dict.end()) return res;
        dict.erase(endWord);
        bool found = false;
        unordered_set<string> q{beginWord}, tmp;
        // Shortest path graph
        unordered_map<string, vector<string> > graph;
        int len = beginWord.size();
        while(!q.empty() && !found) {
            // Visit marking
            for(const string& w : q)
                dict.erase(w);

            for(const string& w : q) {
                string word = w;
                for(int i=0;i<len;++i) {
                    char oldch = word[i];
                    for(int j='a';j<='z';++j) {
                        word[i]=j;
                        if (word == endWord) {
                            // Found end word, exit this level search
                            found=true;
                            // w and word are adjacent nodes
                            graph[w].push_back(word);
                        } else if (dict.find(word)!=dict.end() && !found) {
                            tmp.insert(word);
                            graph[w].push_back(word);
                        }
                    }
                    word[i]=oldch;
                }
            }
            
            swap(q, tmp);
            tmp.clear();
        }
        
        if (found) {
            vector<string> path{beginWord};
            // Recursive backtracking generates all paths
            DFS(beginWord, endWord, graph, path, res);
        }
        return res;
    }
    
private:
    void DFS(const string &word, const string& endWord, const unordered_map<string, vector<string>>& g,
            vector<string>& path,
            vector<vector<string>>& res) {
        if (path.back()==endWord) {
            res.push_back(path);
            return;
        }
        
        if (g.find(word)==g.end()) return;
        
        for(auto child : g.at(word)) {
            path.push_back(child);
            DFS(child, endWord, g, path, res);
            path.pop_back();
        }
    }
};

    Bidirectional BFS:

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord)==dict.end()) return res;
        dict.erase(endWord);
        bool found = false;
        bool backward = false;
        unordered_set<string> q{beginWord}, p{endWord}, tmp;
        unordered_map<string, vector<string> > graph;
        int len = beginWord.size();
        while(!q.empty() && !p.empty() && !found) {
            for(const string& w : q)
                dict.erase(w);
            for(const string& w : q)
                dict.erase(w);
            
            // When swapping dual queues, note reversal of connection relationships
            if (q.size() > p.size()) {
                swap(q, p);
                backward=!backward;
            }
            
            for(const string& w : q) {
                string word = w;
                for(int i=0;i<len;++i) {
                    char oldch = word[i];
                    for(int j='a';j<='z';++j) {
                        word[i]=j;
                        if (p.find(word) != p.end()) {
                            found=true;
                            if (!backward)
                                graph[w].push_back(word);
                            else
                                graph[word].push_back(w);
                        } else if (dict.find(word)!=dict.end() && !found) {
                            tmp.insert(word);
                            if (!backward)
                                graph[w].push_back(word);
                            else
                                graph[word].push_back(w);
                        }
                    }
                    word[i]=oldch;
                }
            }
            
            swap(q, tmp);
            tmp.clear();
        }
        
        if (found) {
            vector<string> path{beginWord};
            DFS(beginWord, endWord, graph, path, res);
        }
        return res;
    }
    
private:
    void DFS(const string &word, const string& endWord, const unordered_map<string, vector<string>>& g,
            vector<string>& path,
            vector<vector<string>>& res) {
        if (path.back()==endWord) {
            res.push_back(path);
            return;
        }
        
        if (g.find(word)==g.end()) return;
        
        for(auto child : g.at(word)) {
            path.push_back(child);
            DFS(child, endWord, g, path, res);
            path.pop_back();
        }
    }
};

    Key Takeaways

    1. Bidirectional BFS reduces search levels
    2. Use set instead of queue when you need both traversal and lookup capabilities

    #Interview #BidirectionalBFS #BFS

    Word Break Problems