1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

struct NodeString {
    vector<NodeString *> before;
    string now;
};
class Solution {
public:
    vector<vector<string>> result;
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        result.clear();
        if (dict.find(start) == dict.end()) {
            dict.insert(start);
        }
        if (dict.find(end) == dict.end()) {
            dict.insert(end);
        }
        map<string, NodeString *> maps;
        maps.clear();
        maps.insert(map<string, NodeString *>::value_type(start, NULL));
        vector<NodeString *> strs, strsc;
        strs.clear();
        NodeString *nodeString = new NodeString();
        nodeString->before.clear();
        nodeString->now = start;
        strs.push_back(nodeString);
        bool isFind = false;
        while (true) {
            map<string, NodeString *> mapstmp;
            mapstmp.clear();
            strsc.clear();
            for (int i = 0; i < strs.size(); i++) {
                string item = strs[i]->now;
                for (int j = 0; j < item.length(); j++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        string tmp = item;
                        if (c != item[j]) {
                            tmp[j] = c;
                            if (dict.find(tmp) != dict.end()) {
                                if (maps.find(tmp) == maps.end()) {
                                    NodeString *nodetmp = new NodeString();
                                    nodetmp->before.clear();
                                    nodetmp->before.push_back(strs[i]);
                                    nodetmp->now = tmp;
                                    if (tmp == end) {
                                        isFind = true;
                                        vector<string> items;
                                        items.clear();
                                        // items.push_back(end);
                                        genResult(nodetmp, items);
                                        continue;
                                    }
                                    strsc.push_back(nodetmp);
                                    maps.insert(map<string, NodeString *>::value_type(tmp, nodetmp));
                                    mapstmp.insert(map<string, NodeString *>::value_type(tmp, nodetmp));
                                } else {
                                    if (tmp != start) {
                                        map<string, NodeString *>::iterator it = mapstmp.find(tmp);
                                        if (it != mapstmp.end())
                                            it->second->before.push_back(strs[i]);
                                    }
                                }
                            }
                        }
                    }
                }
            }

            if (strsc.size() == 0 || isFind) break;
            strs.clear();
            for (int i = 0; i < strsc.size(); i++) {
                strs.push_back(strsc[i]);
            }
        }
        return result;
    }

private:
    void genResult(NodeString *nodeString, vector<string> &items) {
        if (nodeString->before.size() == 0) {
            items.push_back(nodeString->now);
            vector<string> itemsr;
            itemsr.clear();
            vector<string>::reverse_iterator rit;
            for (rit = items.rbegin(); rit != items.rend(); rit++) {
                itemsr.push_back(*rit);
            }
            result.push_back(itemsr);
            items.pop_back();
        } else {
            for (int i = 0; i < nodeString->before.size(); i++) {
                items.push_back(nodeString->now);
                genResult(nodeString->before[i], items);
                items.pop_back();
            }
        }
    }
};