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上有类似的题目和。我们的方法是写一个get_one_edit_words()函数，来返回某一个单词变动一个字母的所有可能情况，然后我们在transform函数中先将开始的单词存入一个队列queue中，还需要一个set来记录所有访问过的单词，还需要哈希表来建立当前单词和变换一步后的单词之间的映射，然后开始类似BFS的遍历，对于每一个单词，遍历get_one_edit_words()函数返回的结果，如果变换后的单词就是目标单词，则我们完成了变换，根据backtrack将整个路径上的单词存入结果中，如果变换单词不是目标单词，但是在字典中，如果没有在字典中，则我们将其排入queue，并加入visited，和建立哈希表的映射，继续遍历，参见代码如下：

 

set
     
       get_one_edit_words(string word) {    set
      
        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
       
         transform(string start, string end, set
        
          dict) {    queue
         
           q;    set
          
            visited; unordered_map
           
             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
            
              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 {};}
            
           
          
         
        
       
      
     

 

类似题目：