Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
题意：给定一个起始单词和一个结束单词，还有一个单词集合，每次可以变换单词中一个字母，所变换的单词需要在wordList中，求起始到结尾最少需要几次变换。
思路：
- 用深度优先搜索，寻找从起始到结尾的所有方法，然后求这些方法中次数最少的值。
public int minLen = Integer.MAX_VALUE;
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (beginWord.equals(endWord) || wordList == null || wordList.size() == 0) {
return 0;
}
HashSet<String> wordSet = new HashSet<>();
for (String word : wordList) {
wordSet.add(word);
}
searchLadder(beginWord, endWord, wordSet, 1);
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
public void searchLadder(String curWord, String endWord, HashSet<String> wordSet, int step) {
if (curWord.equals(endWord)) {
minLen = Math.min(step, minLen);
return;
}
List<String> words = nextWords(curWord, wordSet);
wordSet.remove(curWord);
for (String word : words) {
searchLadder(word, endWord, wordSet, step + 1);
}
wordSet.add(curWord);
}
public List<String> nextWords(String curWord, HashSet<String> wordSet) {
List<String> words = new ArrayList<>();
for (int i = 0; i < curWord.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == curWord.charAt(i)) {
continue;
}
String next = curWord.substring(0, i) + c + curWord.substring(i+1);
if (wordSet.contains(next)) {
words.add(next);
}
}
}
return words;
}
-
宽度优先搜索。
深度搜索会有很多重复计算的步骤，如abb到bcb,集合是[abc, acc, acb]，abb->acb->bcb是最简变换，但是深度优先搜索会找出abb->abc->acc->acb->bcb。
宽度优先搜索，把每个单词下次可能变换出的单词都找出来，放到队列中，找出的单词如果之前出现过就过滤掉，因为这些词出现在当前位置肯定不是最短变换方法，这样就能过滤掉很多不需要统计的变换方法。public int ladderLength(String start, String end, List<String> dict) { HashSet<String> words = new HashSet<>(); for (String word : dict) { words.add(word); } // Use queue to help BFS Queue<String> queue = new LinkedList<String>(); queue.add(start); queue.add(null); // Mark visited word Set<String> visited = new HashSet<String>(); visited.add(start); int level = 1; while (!queue.isEmpty()) { String str = queue.poll(); if (str != null) { // Modify str's each character (so word distance is 1) for (int i = 0; i < str.length(); i++) { char[] chars = str.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { chars[i] = c; String word = new String(chars); // Found the end word if (word.equals(end) && words.contains(word)) return level + 1; // Put it to the queue if (words.contains(word) && !visited.contains(word)) { queue.add(word); visited.add(word); } } } } else { level++; if (!queue.isEmpty()) { queue.add(null); } } } return 0; }
