学步园

题目

原文：

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.
EXAMPLE:
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

译文：

给两个长度相等并在字典存在的单词，写一个方法将一个单词转变为另一个单词，每次只能改变一个字母，并且每次新的单词都可以在字典中找到。

例如：

输入：DAMP, LIKE

输出：DAMP->LAMP->LIMP->LIME->LIKE

解答

ctci解法：

虽然这个问题似乎很难，它实际上是一个简单的修改breadth-first-search。每个单词在我们的“图”分支的所有单词在字典里是一个编辑。有趣的部分是如何实现它，我们应该构建一个图去吗?我们可以,但有一个更简单的方法。我们可以用一个“回溯地图。“在这回溯地图,如果B[v]=
w,然后你知道你编辑v获取w。当我们到达结束的单词,我们可以使用此回溯地图反复扭转我们的路径。看下面的代码:

LinkedList<String> transform(String startWord, String stopWord,Set<String> dictionary) {
	startWord = startWord.toUpperCase();
	stopWord = stopWord.toUpperCase();
	Queue<String> actionQueue = new LinkedList<String>();
	Set<String> visitedSet = new HashSet<String>();
	Map<String, String> backtrackMap = new TreeMap<String, String>();

	actionQueue.add(startWord);
	visitedSet.add(startWord);

	while (!actionQueue.isEmpty()) {
		String w = actionQueue.poll();
		// For each possible word v from w with one edit operation
		for (String v : getOneEditWords(w)) {
			if (v.equals(stopWord)) {
				// Found our word! Now, back track.
				LinkedList<String> list = new LinkedList<String>();
				// Append v to list
				list.add(v);
				while (w != null) {
					list.add(0, w);
					w = backtrackMap.get(w);
				}
				return list;
			}
			// If v is a dictionary word
			if (dictionary.contains(v)) {
				if (!visitedSet.contains(v)) {
					actionQueue.add(v);
					visitedSet.add(v); // mark visited
					backtrackMap.put(v, w);
				}
			}
		}
	}
	return null;
}

Set<String> getOneEditWords(String word) {
	Set<String> words = new TreeSet<String>();
	for (int i = 0; i < word.length(); i++) {
		char[] wordArray = word.toCharArray();
		// change that letter to something else
		for (char c = ‘A’; c <= ‘Z’; c++) {
			if (c != word.charAt(i)) {
				wordArray[i] = c;
				words.add(new String(wordArray));
			}
		}
	}
	return words;
}

n是开始单词的长度,m是同样长度的单词在字典里的数量。该算法的运行时间复杂度是O(n*m)因为while循环将出列最多m个独特的单词。for循环是O(n),因为它遍历字符串应用固定每个字符的替代品的数量。

---EOF---