Skip to content

Instantly share code, notes, and snippets.

@zhuangh
Created February 28, 2018 02:21
Show Gist options
  • Save zhuangh/85e7a23de2c7f28947885de71e2d4ab4 to your computer and use it in GitHub Desktop.
Save zhuangh/85e7a23de2c7f28947885de71e2d4ab4 to your computer and use it in GitHub Desktop.
BFS word ladder problem
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<string> q;
unordered_set<string> m, dict;
q.push(beginWord);
m.insert(beginWord);
for(const auto & it : wordList)
dict.insert(it);
int level = 1;
while(!q.empty()){
queue<string> nex;
while(!q.empty()){
string s = q.front();
q.pop();
if(endWord == s) return level;
for(int i = 0; i < s.size() ; i++){
string t = s;
for(int j = 0; j < 26; j++){
t[i] = 'a'+j;
if(dict.find(t) != dict.end() && m.find(t) == m.end()) {
nex.push(t);
m.insert(t);
}
}
}
}
q = nex;
level++;
}
return 0;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment