18.10 Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
这道题让我们将一个单词转换成另一个单词，每次只能改变一个字母，让我们输出中间转换过程的单词。LeetCode上有类似的题目One Edit Distance和Edit Distance。我们的方法是写一个get_one_edit_words()函数，来返回某一个单词变动一个字母的所有可能情况，然后我们在transform函数中先将开始的单词存入一个队列queue中，还需要一个set来记录所有访问过的单词，还需要哈希表来建立当前单词和变换一步后的单词之间的映射，然后开始类似BFS的遍历，对于每一个单词，遍历get_one_edit_words()函数返回的结果，如果变换后的单词就是目标单词，则我们完成了变换，根据backtrack将整个路径上的单词存入结果中，如果变换单词不是目标单词，但是在字典中，如果没有在字典中，则我们将其排入queue，并加入visited，和建立哈希表的映射，继续遍历，参见代码如下：
set<string> get_one_edit_words(string word) { set<string> res; for (int i = 0; i < word.size(); ++i) { string t = word; for (char c = 'a'; c <= 'z'; ++c) { if (c != word[i]) { t[i] = c; res.insert(t); } } } return res; } vector<string> transform(string start, string end, set<string> dict) { queue<string> q; set<string> visited; unordered_map<string, string> backtrack; q.push(start); visited.insert(start); while (!q.empty()) { string w = q.front(); q.pop(); for (string v : get_one_edit_words(w)) { if (v == end) { vector<string> res{v}; while (!w.empty()) { res.insert(res.begin(), w); w = backtrack[w]; } return res; } if (dict.count(v)) { if (!visited.count(v)) { q.push(v); visited.insert(v); backtrack[v] = w; } } } } return {}; }
本文转自博客园Grandyang的博客，原文链接：单词转换[CareerCup] 18.10 Word Transform ，如需转载请自行联系原博主。