前言

我們社區(qū)陸續(xù)會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者艘儒，ACE 職業(yè)健身教練聋伦。）的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。

LeetCode 算法到目前我們已經(jīng)更新到 125 期界睁，我們會保持更新時(shí)間和進(jìn)度（周一觉增、周三、周五早上 9:00 發(fā)布）翻斟，每期的內(nèi)容不多逾礁，我們希望大家可以在上班路上閱讀，長久積累會有很大提升访惜。

不積跬步嘹履，無以至千里；不積小流债热，無以成江海植捎，Swift社區(qū) 伴你前行。如果大家有建議和意見歡迎在文末留言阳柔，我們會盡力滿足大家的需求焰枢。

難度水平：困難

1. 描述

字典 wordList 中從單詞 beginWord 和 endWord 的 轉(zhuǎn)換序列 是一個(gè)按下述規(guī)格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一對相鄰的單詞只差一個(gè)字母。
• 對于 1 <= i <= k 時(shí)舌剂，每個(gè) si 都在 wordList 中济锄。注意， beginWord 不需要在 wordList 中霍转。
• sk == endWord

給你兩個(gè)單詞 beginWord 和 endWord 和一個(gè)字典 wordList 荐绝，返回 從 beginWord 到 endWord 的 最短轉(zhuǎn)換序列 中的 單詞數(shù)目 。如果不存在這樣的轉(zhuǎn)換序列避消，返回 0 低滩。

2. 示例

示例 1

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
輸出：5
解釋：一個(gè)最短轉(zhuǎn)換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的長度 5。

示例 2

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
輸出：0
解釋：endWord "cog" 不在字典中岩喷，所以無法進(jìn)行轉(zhuǎn)換恕沫。

約束條件：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小寫英文字母組成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

3. 答案

class WordLadder {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
        guard beginWord.count == endWord.count else {
            return 0
        }
        
        var queue = [(beginWord, 1)], wordSet = Set<String>(wordList)
        
        while !queue.isEmpty {
            let (word, step) = queue.removeFirst()
            
            if word == endWord {
                return step
            }
            
            // transform word
            for i in 0..<word.count {
                var wordArray = Array(word)
                
                for char in "abcdefghijklmnopqrstuvwxyz" {
                    guard char != wordArray[i] else {
                        continue
                    }
                    
                    wordArray[i] = char
                    let transformedWord = String(wordArray)
                    
                    guard wordSet.contains(transformedWord) else {
                        continue
                    }
                    
                    wordSet.remove(transformedWord)
                    queue.append((transformedWord, step + 1))
                }
            }
        }
        
        return 0
    }
}

• 主要思想：BFS 檢查所有可能的單詞路徑纱意，直到單詞與結(jié)束單詞完全相同婶溯，然后路徑應(yīng)該是最短的。
• 時(shí)間復(fù)雜度： O(nm)
• 空間復(fù)雜度： O(nm)

N表示單詞的#，m表示單詞的長度

該算法題解的倉庫：LeetCode-Swift

點(diǎn)擊前往 LeetCode 練習(xí)

關(guān)于我們

我們是由 Swift 愛好者共同維護(hù)迄委，我們會分享以 Swift 實(shí)戰(zhàn)褐筛、SwiftUI、Swift 基礎(chǔ)為核心的技術(shù)內(nèi)容叙身，也整理收集優(yōu)秀的學(xué)習(xí)資料渔扎。

后續(xù)還會翻譯大量資料到我們公眾號，有感興趣的朋友信轿，可以加入我們晃痴。