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

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(dict.find(start) == dict.end()) {
            dict.insert(start);
        }
        if(dict.find(end) == dict.end()) {
            dict.insert(end);
        }
        map<string,bool> maps;
        maps.clear();
        maps.insert(map<string,bool>::value_type(start,true));
        vector<string> strs,strsc;
        strs.clear();
        strs.push_back(start);
        int count = 1;
        while(true) {
            strsc.clear();
            count++;
            for(int i = 0;i < strs.size();i++) {
                string item = strs[i];
                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() && maps.find(tmp) == maps.end()) {
                                strsc.push_back(tmp);
                                if(tmp == end) return count;
                                maps.insert(map<string,bool>::value_type(tmp,true));
                            }
                        }
                    }
                }
            }
            if(strsc.size() == 0) break;
            strs.clear();
            for(int i = 0;i < strsc.size();i++) {
                strs.push_back(strsc[i]);
            }
        }
        return 0;
    }
};