LeetCode/126.cpp at master · guihunkun/LeetCode · 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
class Solution
{
	void dfs(unordered_map<string,unordered_set<string> > &trace, const string &last, vector<string> path, vector<vector<string> > &vs)
    {
		path.push_back(last);
		if(trace.count(last)==0)
        {
			reverse(path.begin(),path.end());
			vs.push_back(path);
			return;
		}
		for(const string &word:trace[last])
			dfs(trace,word,path,vs);
	}
public:
	vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList)
    {
		unordered_set<string> dict(wordList.begin(),wordList.end());
		if(dict.count(end)==0)
            return {};
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> q={begin}, dels;
		for(; q.size() && trace.count(end)==0; q=dels)
        {
			for(const string &word:q)
				dict.erase(word);
			dels.clear();
			for(const string &word:q)
            {
				for(int i=0; i<word.length(); ++i)
                {
					string s=word;
					for(char ch='a'; ch<='z'; ++ch)
                    {
						if(word[i]==ch)
                            continue;
						s[i] = ch;
						if(dict.find(s)==dict.end())
                            continue;
						trace[s].insert(word);
						dels.insert(s);
					}
				}
			}
		}
		if(trace.size()==0)
            return {};
		vector<vector<string> > result;
		dfs(trace,end,{},result);
		return result;
	}
};