Algorithm/LeetCode/findLadders.cpp at master · feelpython/Algorithm · GitHub

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
#define CLR(x) memset((x),0,sizeof((x)))
#define MP make_pair
#define MPI make_pair<int, int>
#define PB push_back
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;

class Solution {
public:
    string sst;
    vector<VS> res;
    unordered_map<string, VS> mp;
    VS path;
    void output(string str) {
        path.PB(str);
        if (str == sst) {
            VS tt = path;
            reverse(tt.begin(), tt.end());
            res.PB(tt);
            path.pop_back();
            return;
        }
        REP(i,mp[str].size()) {
            output(mp[str][i]);
        }
        path.pop_back();
    }
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        sst = start;
        mp.clear();
        path.clear();
        res.clear();
        int len = start.length();
        VS que;
        que.push_back(start);
        int st = 0, ed = 0;
        while (st <= ed) {
            int num = ed + 1 - st;
            bool found = false;
            VS del;
            unordered_map<string, bool> dd;
            REP(ii,num) {
                string s = que[st + ii];
                string ss = s;
                if (dd.find(ss) != dd.end()) continue;
                dd[ss] = true;
                bool skip = false;
                REP(i,len) {
                    char bak = s[i];
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        if (ch == s[i]) continue;
                        s[i] = ch;
                        if (s == end) {
                            mp[s].PB(ss);
                            found = true;
                            skip = true;
                            break;
                        }
                        if (dict.find(s) != dict.end()) {
                            mp[s].PB(ss);
                            que.PB(s);
                            del.PB(s);
                        }
                    }
                    if (skip) break;
                    s[i] = bak;
                }
            }
            if (found) {
                output(end);
                break;
            }
            REP(i,del.size()) dict.erase(del[i]);
            st += num;
            ed = que.size() - 1;
        }
        return res;
    }
};

int main() {
    Solution s;
    unordered_set<string> dict;
    /*dict.insert("hot");
      dict.insert("dot");
      dict.insert("dog");
      dict.insert("lot");
      dict.insert("log");
      vector<VS> res = s.findLadders("hit", "cog", dict);*/
    dict.insert("aabaa");
    dict.insert("abbaa");
    dict.insert("baaaa");
    dict.insert("bbaaa");
    dict.insert("bbbaa");
    dict.insert("bbbac");
    vector<VS> res = s.findLadders("aaaaa", "bbbac", dict);
    REP(i,res.size()) {
        REP(j,res[i].size()) cout << res[i][j] << " ";
        cout << endl;
    }
    return 0;
}