?LeetCode刷題實戰(zhàn)127：單詞接龍
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:
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.
題意
每次轉(zhuǎn)換只能改變一個字母。
轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞。
如果不存在這樣的轉(zhuǎn)換序列，返回 0。
所有單詞具有相同的長度。
所有單詞只由小寫字母組成。
字典中不存在重復(fù)的單詞。
你可以假設(shè) beginWord 和 endWord 是非空的，且二者不相同。
示例?1:
輸入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
輸出: 5
解釋: 一個最短轉(zhuǎn)換序列是 "hit"?-> "hot"?-> "dot"?-> "dog"?-> "cog",
?????返回它的長度 5。
示例 2:
輸入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
輸出:?0
解釋:?endWord "cog"?不在字典中，所以無法進行轉(zhuǎn)換。
解題
隊列；
visited 集合。說明：可以直接在 wordSet (由 wordList 放進集合中得到)里做刪除。但更好的做法是新開一個哈希表，遍歷過的字符串放進哈希表里。這種做法具有普遍意義。絕大多數(shù)在線測評系統(tǒng)和應(yīng)用場景都不會在意空間開銷。
方法一：廣度優(yōu)先遍歷
public?class?Solution?{
????public?int?ladderLength(String beginWord, String endWord, ListwordList) ?{
????????// 第 1 步：先將 wordList 放到哈希表里，便于判斷某個單詞是否在 wordList 里
????????SetwordSet = new?HashSet<>(wordList);
????????if?(wordSet.size() == 0?|| !wordSet.contains(endWord)) {
????????????return?0;
????????}
????????wordSet.remove(beginWord);
????????
????????// 第 2 步：圖的廣度優(yōu)先遍歷，必須使用隊列和表示是否訪問過的 visited 哈希表
????????Queuequeue?= new?LinkedList<>();
????????queue.offer(beginWord);
????????Setvisited = new?HashSet<>();
????????visited.add(beginWord);
????????
????????// 第 3 步：開始廣度優(yōu)先遍歷，包含起點，因此初始化的時候步數(shù)為 1
????????int?step = 1;
????????while?(!queue.isEmpty()) {
????????????int?currentSize = queue.size();
????????????for?(int?i = 0; i < currentSize; i++) {
????????????????// 依次遍歷當(dāng)前隊列中的單詞
????????????????String currentWord = queue.poll();
????????????????// 如果 currentWord 能夠修改 1 個字符與 endWord 相同，則返回 step + 1
????????????????if?(changeWordEveryOneLetter(currentWord, endWord, queue, visited, wordSet)) {
????????????????????return?step + 1;
????????????????}
????????????}
????????????step++;
????????}
????????return?0;
????}
????/**
?????* 嘗試對 currentWord 修改每一個字符，看看是不是能與 endWord 匹配
?????*
?????* @param currentWord
?????* @param endWord
?????* @param queue
?????* @param visited
?????* @param wordSet
?????* @return
?????*/
????private?boolean changeWordEveryOneLetter(String currentWord, String endWord,
?????????????????????????????????????????????Queuequeue, Set ?{visited, Set wordSet)
????????char[] charArray = currentWord.toCharArray();
????????for?(int?i = 0; i < endWord.length(); i++) {
????????????// 先保存，然后恢復(fù)
????????????char?originChar = charArray[i];
????????????for?(char?k = 'a'; k <= 'z'; k++) {
????????????????if?(k == originChar) {
????????????????????continue;
????????????????}
????????????????charArray[i] = k;
????????????????String nextWord = String.valueOf(charArray);
????????????????if?(wordSet.contains(nextWord)) {
????????????????????if?(nextWord.equals(endWord)) {
????????????????????????return?true;
????????????????????}
????????????????????if?(!visited.contains(nextWord)) {
????????????????????????queue.add(nextWord);
????????????????????????// 注意：添加到隊列以后，必須馬上標(biāo)記為已經(jīng)訪問
????????????????????????visited.add(nextWord);
????????????????????}
????????????????}
????????????}
????????????// 恢復(fù)
????????????charArray[i] = originChar;
????????}
????????return?false;
????}
}
方法二：雙向廣度優(yōu)先遍歷
public class?Solution?{
????public int ladderLength(String?beginWord, String?endWord, List<String> wordList) {
????????// 第 1 步：先將 wordList 放到哈希表里，便于判斷某個單詞是否在 wordList 里
????????Set<String> wordSet = new?HashSet<>(wordList);
????????if?(wordSet.size() == 0?|| !wordSet.contains(endWord)) {
????????????return?0;
????????}
????????// 第 2 步：已經(jīng)訪問過的 word 添加到 visited 哈希表里
????????Set<String> visited = new?HashSet<>();
????????// 分別用左邊和右邊擴散的哈希表代替單向 BFS 里的隊列，它們在雙向 BFS 的過程中交替使用
????????Set<String> beginVisited = new?HashSet<>();
????????beginVisited.add(beginWord);
????????Set<String> endVisited = new?HashSet<>();
????????endVisited.add(endWord);
????????// 第 3 步：執(zhí)行雙向 BFS，左右交替擴散的步數(shù)之和為所求
????????int step = 1;
????????while?(!beginVisited.isEmpty() && !endVisited.isEmpty()) {
????????????// 優(yōu)先選擇小的哈希表進行擴散，考慮到的情況更少
????????????if?(beginVisited.size() > endVisited.size()) {
????????????????Set<String> temp = beginVisited;
????????????????beginVisited = endVisited;
????????????????endVisited = temp;
????????????}
????????????// 邏輯到這里，保證 beginVisited 是相對較小的集合，nextLevelVisited 在擴散完成以后，會成為新的 beginVisited
????????????Set<String> nextLevelVisited = new?HashSet<>();
????????????for?(String?word : beginVisited) {
????????????????if?(changeWordEveryOneLetter(word, endVisited, visited, wordSet, nextLevelVisited)) {
????????????????????return?step + 1;
????????????????}
????????????}
????????????// 原來的 beginVisited 廢棄，從 nextLevelVisited 開始新的雙向 BFS
????????????beginVisited = nextLevelVisited;
????????????step++;
????????}
????????return?0;
????}
????/**
?????* 嘗試對 word 修改每一個字符，看看是不是能落在 endVisited 中，擴展得到的新的 word 添加到 nextLevelVisited 里
?????*
?????* @param word
?????* @param endVisited
?????* @param visited
?????* @param wordSet
?????* @param nextLevelVisited
?????* @return
?????*/
????private boolean changeWordEveryOneLetter(String?word, Set<String> endVisited,
?????????????????????????????????????????????Set<String> visited,
?????????????????????????????????????????????Set<String> wordSet,
?????????????????????????????????????????????Set<String> nextLevelVisited) {
????????char[] charArray = word.toCharArray();
????????for?(int i = 0; i < word.length(); i++) {
????????????char originChar = charArray[i];
????????????for?(char c = 'a'; c <= 'z'; c++) {
????????????????if?(originChar == c) {
????????????????????continue;
????????????????}
????????????????charArray[i] = c;
????????????????String?nextWord = String.valueOf(charArray);
????????????????if?(wordSet.contains(nextWord)) {
????????????????????if?(endVisited.contains(nextWord)) {
????????????????????????return?true;
????????????????????}
????????????????????if?(!visited.contains(nextWord)) {
????????????????????????nextLevelVisited.add(nextWord);
????????????????????????visited.add(nextWord);
????????????????????}
????????????????}
????????????}
????????????// 恢復(fù)，下次再用
????????????charArray[i] = originChar;
????????}
????????return?false;
????}
}