给定两个有着相同长度且都在字典内的单词,要求写一个方法来把一个单词变型成另一个单词。 一次只能转换一个字母,且每次生成的单词必须在字典内

原创
2016/11/29 09:10
阅读数 324

EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

思路:

这其实就是广度优先遍历。遍历过程中,我们需要记录路径,在找到目标单词后,根据记录的路径打印出变形过程。

BFS的变形体。对起始单词的每一个字母都做替换,把替换后的单词加入到queue中,并同时维护一个Map来记录变化前单词和变化后单词的联系。用来回溯时能打印出路径。

 

 

[java] view plain copy

在CODE上查看代码片派生到我的代码片

  1. package Hard;  
  2.   
  3. import java.util.HashSet;  
  4. import java.util.LinkedList;  
  5. import java.util.Map;  
  6. import java.util.Queue;  
  7. import java.util.Set;  
  8. import java.util.TreeMap;  
  9. import java.util.TreeSet;  
  10.   
  11.   
  12. /** 
  13.  * Given two words of equal length that are in a dictionary,  write a method to  trans- 
  14. form  one word into another word by changing only one letter at a time. The new 
  15. word you get in each step must be in the dictionary. 
  16.  
  17. 给定两个有着相同长度且都在字典内的单词,要求写一个方法来把一个单词变型成另一个单词。 
  18. 一次只能转换一个字母,且每次生成的单词必须在字典内 
  19.  * 
  20.  */  
  21. public class S18_10 {  
  22.   
  23.     public static LinkedList<String> transform(String startWord, String stopWord, Set<String> dictionary) {  
  24.         startWord = startWord.toUpperCase();  
  25.         stopWord = stopWord.toUpperCase();  
  26.         Queue<String> actionQueue = new LinkedList<String>();  
  27.         Set<String> visitedSet = new HashSet<String>();  
  28.         Map<String, String> backtrackMap = new TreeMap<String, String>();  
  29.   
  30.         actionQueue.add(startWord);  
  31.         visitedSet.add(startWord);  
  32.   
  33.         while (!actionQueue.isEmpty()) {  
  34.             String w = actionQueue.poll();  
  35.             // For each possible word v from w with one edit operation  
  36.             for (String v : getOneEditWords(w)) {  
  37.                 if (v.equals(stopWord)) {       // Found our word! Now, back track.  
  38.                     LinkedList<String> list = new LinkedList<String>();  
  39.                     list.add(v);        // Append v to list  
  40.                     while (w != null) {  
  41.                         list.add(0, w);  
  42.                         w = backtrackMap.get(w);  
  43.                     }  
  44.                     return list;  
  45.                 }  
  46.   
  47.                 // If v is a dictionary word  
  48.                 if (dictionary.contains(v)) {  
  49.                     if (!visitedSet.contains(v)) {  
  50.                         actionQueue.add(v);  
  51.                         visitedSet.add(v);          // mark visited  
  52.                         backtrackMap.put(v, w); // w is the previous state of v  
  53.                     }  
  54.                 }  
  55.             }  
  56.         }  
  57.         return null;  
  58.     }  
  59.   
  60.     // 改变word的某一个字母  
  61.     private static Set<String> getOneEditWords(String word) {  
  62.         Set<String> words = new TreeSet<String>();  
  63.           
  64.         for (int i = 0; i < word.length(); i++) {        // for every letter  
  65.             char[] wordArray = word.toCharArray();  
  66.             // change that letter to something else  
  67.             for (char c = 'A'; c <= 'Z'; c++) {  
  68.                 if (c != word.charAt(i)) {  
  69.                     wordArray[i] = c;  
  70.                     words.add(new String(wordArray));  
  71.                 }  
  72.             }  
  73.         }  
  74.         return words;  
  75.     }  
  76.   
  77.     public static HashSet<String> setupDictionary(String[] words) {  
  78.         HashSet<String> hash = new HashSet<String>();  
  79.         for (String word : words) {  
  80.             hash.add(word.toUpperCase());  
  81.         }  
  82.         return hash;  
  83.     }  
  84.   
  85.     public static void main(String[] args) {  
  86.         String[] words = { "maps", "tan", "tree", "apple", "cans", "help",  
  87.                 "aped", "free", "apes", "flat", "trap", "fret", "trip", "trie",  
  88.                 "frat", "fril" };  
  89.         HashSet<String> dict = setupDictionary(words);  
  90.         LinkedList<String> list = transform("tree", "flat", dict);  
  91.         for (String word : list) {  
  92.             System.out.println(word);  
  93.         }  
  94.     }  
  95. }  
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部