Word Ladder from LeetCode OnlineJudge

word_ladder.cpp

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        dict.insert(start); dict.insert(end);
        queue< pair<string, int> > q;
        unordered_set<string> visited;
        q.push(make_pair(start, 1));
        int res = 0;
        while (!q.empty()) {
            pair<string, int> top = q.front();
            q.pop();
            visited.insert(top.first);
            string str = top.first;
            for (int i=0; i<str.size(); ++i) {
                char record = str[i];
                for (char c='a'; c <= 'z'; ++c) {
                    if (str[i] == c) continue;
                    str[i] = c;
                    if (dict.find(str) != dict.end() 
                            && visited.find(str) == dict.end()) {
                        if (str == end) {
                            res = top.second + 1;
                            goto END; // evil goto
                        }
                        q.push(make_pair(str, top.second+1));
                        
                        // difference between 4.71s and 0.17s!!!
                        dict.erase(str); 
                    }
                }
                str[i] = record;
            }
        }
        END:
        return res;
    }
};