Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
http://www.lintcode.com/en/problem/word-ladder/
Discussion
非常典型的BFS。用两个队列，current, next，分别表示当前层次和下一层，另设一个全局整数level，表
示层数（也即路径长度），当碰到目标状态，输出level 即可。
用unordered_set来实现判重。
在状态转移的时候，也就是改变一个字母以后，查该单词是否在词典中，而不要去对每个单词查词典里是否有距离为1的单词.
Solution
写这个题之前先写一遍level order traversal，熟悉BFS框架。
- 改成用一个queue
- 不需要额外的isVisted这个hash set,每次新的word记录到queue里的时候就把它从dict里面erase掉。
int ladderLength(string start, string end, unordered_set<string> &dict) {
// write your code here
int n = start.length();
if(n==0 || n!=end.length() || dict.empty()) {
return 0;
}
queue<string> currentNodes;
int len = 2;
currentNodes.emplace(start);
dict.erase(start);
while(currentNodes.empty() == false) {
int sz = currentNodes.size();//for each word in the current level
for(int i=0; i<sz; i++) {
string newStr = currentNodes.front();
currentNodes.pop();
for(int j=0; j<n; j++) {//for each letter in the current node
char tmp = newStr[j];
for(char c = 'a'; c<='z'; c++) {
if(c==tmp) continue;
newStr[j] = c;
if(newStr == end) {
return len;
}
if(dict.find(newStr) != dict.end()) {
currentNodes.push(newStr);
dict.erase(newStr);
}
newStr[j] = tmp;
}
}
}
len++;
}
return 0;
}
下面的写法思路更清晰，BFS，只是每个node的neighbors要自己去算而已。
Follow up
最爱下面这个写法。
// Time: O(n * d), n is length of the string, d is size of the dictionary
// Space: O(d)
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
int n = start.length();
queue<string> level;
int len = 1;
level.emplace(start);
while(level.empty() == false) {
int current_size = level.size();
for(int i=0; i<current_size; i++) {
string cur = level.front();
if(cur == end) return len;
dict.erase(cur);
level.pop();//remove cur from level
bfs(cur, dict, level);//, update level with cur's neighbors
}
len++;
}
return 0;
}
void bfs(string s, unordered_set<string> &dict, queue<string> &level) {
int n = s.length();
for(int i=0; i<n; i++) {
string tmp = s;
for(char c = 'a'; c <= 'z'; c++) {
tmp[i] = c;
if(dict.find(tmp) != dict.end()) {
level.emplace(tmp);
dict.erase(tmp);//这里是为了make sure同一层不要有重复的word
}
}
}
}
};
用显式的两层level来写。方便扩展到下一题。
class Solution {
public:
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
int ladderLength(string start, string end, unordered_set<string> &dict) {
int len = 0;
if(start == end) return 2;
unordered_set<string> level[2];//level[0]: current level, level[1]: next level
level[len].emplace(start);
unordered_set<string> visited;
while(level[len%2].size() >0) {
for(auto const& s : level[len%2]) {
if(s == end) {
return len +1;
}
visited.emplace(s); // mark as visited before next level
//get s's neighbors, i.e., one distance words in dict
bfs(s, dict, visited, level[(len+1)%2]);
}
level[len%2].clear();
len++;
}
return len + 1;
}
void bfs(string s, unordered_set<string> &dict, unordered_set<string> &visited,
unordered_set<string> &nextlevel) {
int n = s.length();
for(int i=0; i<n; i++) {
for(char c = 'a'; c<='z'; c++) {
string tmp = s;
tmp[i] = c;
if(dict.find(tmp) != dict.end() && visited.find(tmp) == visited.end()) {
nextlevel.emplace(tmp);
//visited.emplace(tmp);//因为nextlevel用的unordered_set,同一层不可能有重复的了，如果是用vector的话这句就不能注释掉，因为同一层有重复的提交的时候会超时。
}
}
}
}
};
下面这个是双向的BFS，太高级了，leetcode上提交80ms，几乎最快。
//BFS， two-end method
//traverse the path simultaneously from start node and end node, and merge in the middle
//the speed will increase (logN/2)^2 times compared with one-end method
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_set<string> begSet, endSet, *set1, *set2;
begSet.insert(start);
endSet.insert(end);
int h=1, K=start.size();
while(!begSet.empty()&&!endSet.empty()){
if(begSet.size()<=endSet.size()){ //Make the size of two sets close for optimization
set1=&begSet; //set1 is the forward set
set2=&endSet; //set2 provides the target node for set1 to search
}
else{
set1=&endSet;
set2=&begSet;
}
unordered_set<string> itmSet; //intermediate Set
h++;
for(auto i=set1->begin();i!=set1->end();i++){
string cur=*i;
for(int k=0;k<K;k++){ //iterate the characters in string cur
char temp=cur[k];
for(int l=0;l<26;l++){ //try all 26 alphabets
cur[k]='a'+l;
auto f=set2->find(cur);
if(f!=set2->end())return h;
f=dict.find(cur);
if(f!=dict.end()){
itmSet.insert(cur);
dict.erase(f);
}
}
cur[k]=temp;
}
}
swap(*set1, itmSet);
}
return 0;
}