Edit Distance

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<pair<string, int> > q;
        q.push(make_pair(beginWord, 1));

        while (!q.empty()) {
            pair<string, int> poped = q.front(); q.pop();
            if (poped.first == endWord) {
                return poped.second;
            } else {
                string poped_str = poped.first;
                for (int i = 0; i < poped_str.size(); i++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (poped_str[i] != ch) {
                            char temp = poped_str[i];
                            poped_str[i] = ch;
                            if (dict.count(poped_str)) {
                                q.push(make_pair(poped_str, poped.second + 1));
                                dict.erase(poped_str);
                            }
                            poped_str[i] = temp;
                        }
                    }
                }
            }
        }
        return 0;
    }
};