U*********y
发帖数: 54 | 1 题目: transform one word into another, 1 letter at a time, each step must
be
in the dictionary.
CareerCup的BFS解看起来很麻烦, 既然没要求最短距离转换或得出所有可能转换, 就写
了个DFS+backtracking的解, 请指教!
[code]
unordered_set dict; //dictionary
bool validTran(string &a, string &b, int d, unordered_map
string> &path) {
if(a == b) {
return 1;
}
if(d == b.size()) return 0;
if(a[d] == b[d]) { //no change at this position is needed
return validTran(a, b, d+1, path);
}
for(char ch = 'a'; ch <= 'z'; ch++) {
if(ch == a[d]) continue;
string t(a);
t[d] = ch;
if(dict.count(t) && validTran(t, b, d+1, path)) {
path[a] = t;
return 1;
}
}
return 0;
}
[/code] |
|
