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.
題意：給定一個(gè)起始單詞和一個(gè)結(jié)束單詞拓颓，還有一個(gè)單詞集合，每次可以變換單詞中一個(gè)字母狮斗，所變換的單詞需要在wordList中脆淹，求起始到結(jié)尾最少需要幾次變換。
思路：
- 用深度優(yōu)先搜索凝果，尋找從起始到結(jié)尾的所有方法汇在，然后求這些方法中次數(shù)最少的值浓恳。
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;
}
-
寬度優(yōu)先搜索煮嫌。
深度搜索會(huì)有很多重復(fù)計(jì)算的步驟笛谦，如abb到bcb,集合是[abc, acc, acb]，abb->acb->bcb是最簡變換昌阿，但是深度優(yōu)先搜索會(huì)找出abb->abc->acc->acb->bcb饥脑。
寬度優(yōu)先搜索，把每個(gè)單詞下次可能變換出的單詞都找出來懦冰，放到隊(duì)列中灶轰，找出的單詞如果之前出現(xiàn)過就過濾掉，因?yàn)檫@些詞出現(xiàn)在當(dāng)前位置肯定不是最短變換方法儿奶，這樣就能過濾掉很多不需要統(tǒng)計(jì)的變換方法框往。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; }
