Word Ladder II Solutions in C++

// Source : https://oj.leetcode.com/problems/word-ladder-ii/
// Author : Hao Chen
// Date   : 2014-10-13



#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <unordered_set>
using namespace std;

// Solution
//
//      1) Using BSF algorithm build a tree like below
//      2) Using DSF to parse the tree to the transformation path.
//
// For example:
//
//     start = "hit"
//     end = "cog"
//     dict = ["hot","dot","dog","lot","log","dit","hig", "dig"]
//
//                      +-----+
//        +-------------+ hit +--------------+
//        |             +--+--+              |
//        |                |                 |
//     +--v--+          +--v--+           +--v--+
//     | dit |    +-----+ hot +---+       | hig |
//     +--+--+    |     +-----+   |       +--+--+
//        |       |               |          |
//        |    +--v--+         +--v--+    +--v--+
//        +----> dot |         | lot |    | dig |
//             +--+--+         +--+--+    +--+--+
//                |               |          |
//             +--v--+         +--v--+       |
//        +----> dog |         | log |       |
//        |    +--+--+         +--+--+       |
//        |       |               |          |
//        |       |    +--v--+    |          |
//        |       +--->| cog |<-- +          |
//        |            +-----+               |
//        |                                  |
//        |                                  |
//        +----------------------------------+

map< string, unordered_set<string> >& 
buildTree(string& start, string& end, unordered_set<string> &dict) {

    static map< string, unordered_set<string> > parents;
    parents.clear();

    unordered_set<string> level[3];
    unordered_set<string> *previousLevel = &level[0];
    unordered_set<string> *currentLevel = &level[1];
    unordered_set<string> *newLevel = &level[2];
    unordered_set<string> *p =NULL;
    currentLevel->insert(start);

    bool reachEnd = false;

    while( !reachEnd ) {
        newLevel->clear();
        for(auto it=currentLevel->begin(); it!=currentLevel->end(); it++) {    
            for (int i=0; i<it->size(); i++) {
                string newWord = *it;
                for(char c='a'; c<='z'; c++){
                    newWord[i] = c;
                    if (newWord == end){
                        reachEnd = true;
                        parents[*it].insert(end);
                        continue;
                    }
                    if ( dict.count(newWord)==0 || currentLevel->count(newWord)>0 || previousLevel->count(newWord)>0 ) {
                        continue;
                    }
                    newLevel->insert(newWord);
                    //parents[newWord].insert(*it);
                    parents[*it].insert(newWord);
                }
            }
        } 
        if (newLevel->empty()) break;

        p = previousLevel; 
        previousLevel = currentLevel;
        currentLevel = newLevel;
        newLevel = p;
    }


    if ( !reachEnd ) {
        parents.clear();
    } 
    return parents;
}

void generatePath( string start, string end,
        map< string, unordered_set<string> > &parents, 
        vector<string> path,
        vector< vector<string> > &paths) {

    if (parents.find(start) == parents.end()){
        if (start == end){
            paths.push_back(path);
        }
        return;
    }

    for(auto it=parents[start].begin(); it!=parents[start].end(); it++){
        path.push_back(*it);
        generatePath(*it, end, parents, path, paths);
        path.pop_back();
    }

}

vector< vector<string> > 
findLadders(string start, string end, unordered_set<string> &dict) {

    vector< vector<string> > ladders;
    vector<string> ladder;
    ladder.push_back(start);
    if (start == end){
        ladder.push_back(end);
        ladders.push_back(ladder);
        return ladders;
    }

    map< string, unordered_set<string> >& parents = buildTree(start, end, dict);

    if  (parents.size()<=0) {
        return ladders;
    }

    generatePath(start, end, parents, ladder, ladders);

    return ladders;
}

void printLadders(vector< vector<string> > &ladders){
    int i, j;
    for (i=0; i<ladders.size(); i++){
        for (j=0; j<ladders[i].size()-1; j++){
            cout << ladders[i][j] << " -> ";
        }
        cout << ladders[i][j] << endl; 
    }
}

int main(int argc, char** argv)
{
    string start = "hit";
    string end = "cog";
    //unordered_set<string> dict ({"hot","dot","dog","lot","log"});
    unordered_set<string> dict ({"bot","cig", "cog", "dit", "dut", "hot", "hit" ,"dot","dog","lot","log"});

    vector< vector<string> > ladders;
    ladders = findLadders(start, end, dict);
    printLadders(ladders);
    return 0;
}

#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    ListNode* reverseList(ListNode *head) {
        ListNode *newHead = NULL;
        while (head) {
            ListNode *next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }

    ListNode *shuffleMerge(ListNode *a, ListNode *b) {
        ListNode *ret = NULL, **lastRef = &ret;
        while (a && b) {
            moveNode(lastRef, &a);
            lastRef = &((*lastRef)->next);
            moveNode(lastRef, &b);
            lastRef = &((*lastRef)->next);
        }
        *lastRef = a ? a : b;
        return ret;
    }

    void moveNode(ListNode **destRef, ListNode **sourceRef) {
        ListNode *newNode = *sourceRef;
        *sourceRef = newNode->next;
        newNode->next = *destRef;
        *destRef = newNode;
    }

public:
    void reorderList(ListNode *head) {
        if (head == NULL) return;
        ListNode *slow = head, *fast = head->next;
        while (fast) {
            fast = fast->next;
            if (fast) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        ListNode *back = reverseList(slow->next);
        slow->next = NULL;
        head = shuffleMerge(head, back);
    }
};

/// Source : https://leetcode.com/problems/word-ladder-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
#include <unordered_map>

using namespace std;

/// BFS
/// Time Complexity: O(n*n)
/// Space Complexity: O(n)
class Solution {

public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

        int end = find(wordList.begin(), wordList.end(), endWord) - wordList.begin();
        if(end == wordList.size())
            return {};

        int begin = find(wordList.begin(), wordList.end(), beginWord) - wordList.begin();
        if(begin == wordList.size())
            wordList.push_back(beginWord);

        int n = wordList.size();

        // Create Graph
        vector<vector<int>> g(n, vector<int>());
        for(int i = 0 ; i < wordList.size() ; i ++)
            for(int j = i + 1 ; j < wordList.size() ; j ++)
                if(similar(wordList[i], wordList[j])){
                    g[i].push_back(j);
                    g[j].push_back(i);
                }

        unordered_map<int, int> distance;
        bfs(g, begin, end, distance);

        vector<vector<string>> res;
        vector<int> tres = {begin};
        getRes(g, begin, end, distance, wordList, tres, res);

        return res;
    }

private:
    void bfs(const vector<vector<int>>& g, int begin, int end,
             unordered_map<int, int>& distance){

        queue<int> q;
        q.push(begin);
        distance[begin] = 0;

        while(!q.empty()){
            int cur = q.front();
            q.pop();
            // assert(distance.find(cur) != distance.end());

            for(int j: g[cur])
                if(distance.find(j) == distance.end()){
                    distance[j] = distance[cur] + 1;
                    q.push(j);
                }
        }
    }

    void getRes(vector<vector<int>>& g, int cur, int end,
                unordered_map<int, int>& distance,
                const vector<string>& wordList,
                vector<int>& tres, vector<vector<string>>& res){

        if(tres.size() > 0 && tres[tres.size() - 1] == end){
            res.push_back(getPath(tres, wordList));
            return;
        }

        for(int i: g[cur])
            if(distance[i] == distance[cur] + 1){
                tres.push_back(i);
                getRes(g, i, end, distance, wordList, tres, res);
                tres.pop_back();
            }

        return;
    }

    vector<string> getPath(const vector<int>& path,
                           const vector<string>& wordList){
        vector<string> ret;
        for(const int e: path)
            ret.push_back(wordList[e]);
        return ret;
    }

    bool similar(const string& word1, const string& word2){

        // assert(word1 != "" && word1.size() == word2.size() && word1 != word2);

        int diff = 0;
        for(int i = 0 ; i < word1.size() ; i ++)
            if(word1[i] != word2[i]){
                diff ++;
                if(diff > 1)
                    return false;
            }
        return true;
    }
};


void print_vector_vector(const vector<vector<string>>& res){
    for(const vector<string>& v: res){
        for(const string& e: v)
            cout << e << " ";
        cout << endl;
    }
    cout << endl;
}

int main() {

    vector<string> vec1 = {"hot","dot","dog","lot","log","cog"};
    string beginWord1 = "hit";
    string endWord1 = "cog";
    vector<vector<string>> res1 = Solution().findLadders(beginWord1, endWord1, vec1);
    print_vector_vector(res1);

    // ---

    vector<string> vec2 = {"a","b","c"};
    string beginWord2 = "a";
    string endWord2 = "c";
    vector<vector<string>> res2 = Solution().findLadders(beginWord2, endWord2, vec2);
    print_vector_vector(res2);

    return 0;
}