| 13 | public class Question { |
| 14 | |
| 15 | public static LinkedList<String> transform(String startWord, String stopWord, Set<String> dictionary) { |
| 16 | startWord = startWord.toUpperCase(); |
| 17 | stopWord = stopWord.toUpperCase(); |
| 18 | Queue<String> actionQueue = new LinkedList<String>(); |
| 19 | Set<String> visitedSet = new HashSet<String>(); |
| 20 | Map<String, String> backtrackMap = new TreeMap<String, String>(); |
| 21 | |
| 22 | actionQueue.add(startWord); |
| 23 | visitedSet.add(startWord); |
| 24 | |
| 25 | while (!actionQueue.isEmpty()) { |
| 26 | String w = actionQueue.poll(); |
| 27 | // For each possible word v from w with one edit operation |
| 28 | for (String v : getOneEditWords(w)) { |
| 29 | if (v.equals(stopWord)) { |
| 30 | // Found our word! Now, back track. |
| 31 | LinkedList<String> list = new LinkedList<String>(); |
| 32 | // Append v to list |
| 33 | list.add(v); |
| 34 | while (w != null) { |
| 35 | list.add(0, w); |
| 36 | w = backtrackMap.get(w); |
| 37 | } |
| 38 | return list; |
| 39 | } |
| 40 | |
| 41 | // If v is a dictionary word |
| 42 | if (dictionary.contains(v)) { |
| 43 | if (!visitedSet.contains(v)) { |
| 44 | actionQueue.add(v); |
| 45 | visitedSet.add(v); // mark visited |
| 46 | backtrackMap.put(v, w); |
| 47 | } |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | return null; |
| 52 | } |
| 53 | |
| 54 | private static Set<String> getOneEditWords(String word) { |
| 55 | Set<String> words = new TreeSet<String>(); |