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