• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode127.单词接龙|WordLadder

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

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.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  • 如果不存在这样的转换序列,返回 0。
  • 所有单词具有相同的长度。
  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中,所以无法进行转换。

304ms
 1 class Solution {
 2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
 3         if !wordList.contains(endWord) 
 4         { 
 5             return 0 
 6         }
 7         
 8         let dict = Set(wordList)
 9         var beginSet = Set<String>()
10         var endSet = Set<String>()
11         var visitedSet = Set<String>()
12         var length = 1
13         var found = false
14         
15         beginSet.insert(beginWord)
16         endSet.insert(endWord)
17         
18         while !found && !beginSet.isEmpty && !endSet.isEmpty {
19             var nextSet = Set<String>()
20             //accelerating search speed by swap begin and end
21             if beginSet.count > endSet.count {
22                 swap(&beginSet, &endSet)
23             }
24             found = helper(beginSet, endSet, dict, &visitedSet, &nextSet)
25             beginSet = nextSet
26             length += 1
27         }
28         return found ? length : 0
29     }
30     
31     private func helper(_ beginSet: Set<String>, _ endSet: Set<String>, _ dict: Set<String>,
32                         _ visitedSet: inout Set<String>, _ resSet: inout Set<String>) -> Bool {
33         
34         let alphaArray = Array("abcdefghijklmnopqrstuvwxyz")
35         
36         for word in beginSet {
37             for i in 0 ..< word.count {
38                 var chars = Array(word)
39                 for j in 0 ..< alphaArray.count{
40                     chars[i] = alphaArray[j]
41                     let str = String(chars)
42                     if dict.contains(str) {
43                         if endSet.contains(str) 
44                         { 
45                             return true 
46                         }
47                         if !visitedSet.contains(str) 
48                         { 
49                             resSet.insert(str)
50                             visitedSet.insert(str) 
51                         }
52                     }
53                 }
54             }
55         }
56         return false
57     }
58 }

884ms

 1 class Solution {
 2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
 3         // ensure the endWord is in the wordList
 4         if !wordList.contains(endWord) {
 5             return 0
 6         }
 7 
 8         // build a word map with char array representations
 9         // this saves an enormous amount of time
10         var wordMap: [String: [Character]] = [:]
11         for i in 0..<wordList.count {
12             // beginWord should never be in the list
13             if wordList[i] == beginWord {
14                 continue
15             }
16             wordMap[wordList[i]] = [Character](wordList[i].characters)
17         }
18         
19         // we work the problem from the begining forward and end backwards
20         // this allows us to deal with the smallest set of possibilities in 
21         // both "directions"
22         var beginMap:[String: [Character]] = [beginWord: [Character](beginWord.characters)]
23         var endMap:[String: [Character]] = [endWord: [Character](endWord.characters)]
24         
25         // burnedMap bridges what has been used in both beginMap or endMap
26         var burnedMap:[String: [Character]] = [:]
27         
28         // word len is stable throughout the iterations, pay for it only once
29         let wordLen = beginWord.count
30         
31         // mutations tracts how many time mutated on the road from beginWord to endWord
32         var mutations = 1
33 
34         // we continue while beginMap and endMap are non-empty
35         // if one empties, there is no path from beginWord to endWord
36         while !beginMap.isEmpty && !endMap.isEmpty {
37             // minimize the working set by swapping in the smaller
38             // set, we only care about the mutation count
39             if beginMap.count > endMap.count {
40                 let tempMap = beginMap
41                 beginMap = endMap
42                 endMap = tempMap
43             }
44 
45             // track the upcoming set of mutation candidates we're about to create
46             var newMap: [String: [Character]] = [:]
47 
48             // iterate throught he last set of mutation candidates
49             for candidateKV in beginMap {
50                 let candidateChars = candidateKV.value
51                 
52                 // walk through all the remaining (un-burned) valid words
53                 for wordKV in wordMap {
54                     let word = wordKV.key
55                     let wordChars = wordKV.value
56                     
57                     // diff the candidate and valid words looking
58                     // fir diffs of 1 character
59                     var diffs = 0
60                     
61                     for i in 0..<wordLen {
62                         if candidateChars[i] != wordChars[i] {
63                             diffs += 1
64                             if diffs > 1 {
65                                 break
66                             }
67                         }
68                     }
69                     
70                     // anything other than a diff of 1 is not applicable
71                     // in this loop, we can only consider "word" if the
72                     // diff is exactly 1
73                     if diffs == 1 {
74                         // we have a valid 1 character diff, use it
75                         
76                         if endMap[word] != nil {
77                             // base case reached
78                             return mutations + 1
79                         }
80                         
81                         if burnedMap[word] == nil {
82                             newMap[word] = wordChars
83                             burnedMap[word] = wordChars
84                         }
85                     }
86                 }
87             }
88             
89             // we already evaluated what was in beginMap, we can 
90             // lose those and use the newMap evaluation set 
91             beginMap = newMap
92             
93             // we have completed an additional mutation step
94             mutations += 1
95         }
96         
97         return 0
98     }
99 }  

1520ms

  1 class Solution {
  2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
  3         //Set类型替换数组类型,加速查找
  4         var wordSet:Set<String> = Set<String>(wordList)
  5         //构建队列,实现广度优先遍历
  6         var q:Queue<String> = Queue<String>()
  7         //加入源顶点
  8         q.enQueue(beginWord)
  9         var res:Int = 0
 10         while (!q.isEmpty())
 11         {
 12             for k in (1...q.count).reversed()
 13             {
 14                 var word:String = q.deQueue()!
 15                 if word == endWord {return res + 1}
 16                 for i in 0..<word.count
 17                 {
 18                     var newWord:String = word
 19                     for ch in 97...122
 20                     {
 21                         newWord[i] = ch.ASCII 
 22                         if wordSet.contains(newWord) && newWord != word
 23                         {
 24                             q.enQueue(newWord)
 25                             wordSet.remove(newWord)
 26                         }
 27                     }
 28                 }
 29             }
 30             res += 1
 31         }
 32          return 0
 33     }
 34 }
 35 
 36 //String扩展方法
 37 extension String {
 38     func toCharArray() -> [Character]
 39     {
 40         var arr:[Character] = [Character]()
 41         for char in self.characters
 42         {
 43             arr.append(char)
 44         }
 45         return arr
 46     }
 47     
 48     //subscript函数可以检索数组中的值
 49     //直接按照索引方式截取指定索引的字符
 50     subscript (_ i: Int) -> Character {
 51         //读取字符
 52         get {return self[index(startIndex, offsetBy: i)]}
 53         
 54         //修改字符
 55         set
 56         {
 57             var str:String = self
 58             var index = str.index(startIndex, offsetBy: i)
 59             str.remove(at: index)
 60             str.insert(newValue, at: index)
 61             self = str
 62         }
 63     }
 64 }
 65 
 66 //Int扩展方法  
 67 extension Int
 68 {
 69     //属性:ASCII值(定义大写为字符值)
 70     var ASCII:Character 
 71     {
 72         get {return Character(UnicodeScalar(self)!)}
 73     }
 74 }
 75 
 76 public struct Queue<T> {
 77     
 78     // 泛型数组:用于存储数据元素
 79     fileprivate var queue: [T] 
 80 
 81     // 返回队列中元素的个数
 82     public var count: Int {
 83         return queue.count
 84     }
 85     
 86     // 构造函数:创建一个空的队列
 87     public init() {
 88         queue = [T]()
 89     }
 90     
 91     //通过既定数组构造队列
 92     init(_ arr:[T]){
 93         queue = arr
 94     }
 95     
 96     // 检查队列是否为空
 97     // - returns: 如果队列为空,则返回true,否则返回false
 98     public func isEmpty() -> Bool {
 99         return queue.isEmpty
100     }
101     
102     // 入队列操作:将元素添加到队列的末尾
103     public mutating func enQueue(_ element: T) {
104         queue.append(element)
105     }
106     
107     // 出队列操作:删除并返回队列中的第一个元素
108     public mutating func deQueue() -> T? {
109         return queue.removeFirst()
110     }
111 }

1692ms

 1 class Solution {
 2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
 3         
 4         var wordSet = Set(wordList)
 5         var level = 0
 6         var currentLevelWords = [beginWord]
 7         
 8         while !currentLevelWords.isEmpty {
 9             level += 1
10             
11             var nextLevelWords: [String] = []
12             
13             for word in currentLevelWords {
14                 if word == endWord {
15                     return level
16                 }
17                 
18                 nextLevelWords += findRelatedWords(word: word, wordSet: &wordSet)
19             }
20             
21             currentLevelWords = nextLevelWords
22         }
23         
24         return 0
25     }
26     
27     private let alphabet = Array("abcdefghijklmnopqrstuvwxyz")
28     
29     func findRelatedWords(word: String, wordSet: inout Set<String>) -> [String] {
30         var relatedWords: [String] = []
31         
32         var word = word
33         var wordIndex = word.startIndex
34         while wordIndex < word.endIndex {
35             
36             let originalCharacter = word[wordIndex]
37             
38             for character in alphabet {
39                 word.remove(at: wordIndex)
40                 word.insert(character, at: wordIndex)
41                 
42                 if wordSet.contains(word) {
43                     wordSet.remove(word)
44                     
45                     relatedWords.append(word)
46                 }
47             }
48             
49             word.remove(at: wordIndex)
50             word.insert(originalCharacter, at: wordIndex)
51             
52             wordIndex = word.index(after: wordIndex)
53         }
54         
55         return relatedWords
56     }
57 }

1788ms

 1 class Solution {
 2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
 3         
 4         var wordSet = Set(wordList)
 5         var currentLevelWords = [beginWord]
 6         var level = 0
 7         
 8         while !currentLevelWords.isEmpty {
 9             level += 1
10             
11             var nextLevelWords: [String] = []
12             
13             for word in currentLevelWords {
14                 
15                 if word == endWord {
16                     return level
17                 }
18                 
19                 nextLevelWords += findCloseWords(word: word, wordSet: &wordSet)
20             }
21             
22             currentLevelWords = nextLevelWords
23         }
24         
25         return 0
26     }
27     
28     let alphabet = Array("abcdefghijklmnopqrstuvwxyz")
29     
30     func findCloseWords(word: String, wordSet: inout Set<String>) -> [String] {
31         
32         var closeWords: [String] = []
33         
34         var word = word
35         var wordIndex = word.startIndex
36         
37         while wordIndex < word.endIndex {
38             
39             let originalCharacter = word[wordIndex]
40             
41             for character in alphabet {
42                 word.remove(at: wordIndex)
43                 word.insert(character, at: wordIndex)
44                 
45                 if wordSet.contains(word) {
46                     closeWords.append(word)
47                     wordSet.remove(word)
48                 }
49             }
50             
51             word.remove(at: wordIndex)
52             word.insert(originalCharacter, at: wordIndex)
53             
54             wordIndex = word.index(after: wordIndex)
55         }
56         
57         return closeWords
58     }
59 }

2284ms

 1 class Solution {
 2     func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
 3         var queue = [beginWord]
 4         var wordList = Set(wordList)
 5         var length = 1
 6 
 7         while !queue.isEmpty && !wordList.isEmpty {
 8             let count = queue.count
 9             for _ in 0..<count {
10                 let word = queue.removeFirst()
11 
12                 let validTransforms = validTransformations(word, wordList)
13                 for nextWord in validTransforms {
14                     if nextWord == endWord {
15                         return length + 1
16                     }
17                     wordList.remove(nextWord)
18                     queue.append(nextWord)
19                 }
20             }
21 
22             length += 1
23         }
24 
25         return 0
26     }
27     
28     func validTransformations(_ word: String, _ wordList: Set<String>) -> [String] {
29         var result = [String]()
30         let alpahabetArray = Array("abcdefghijklmnopqrstuvwxyz".characters)
31         for i in 0 ..< word.characters.count {
32             var chars = Array(word.characters)
33              
                       
                    
                    

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift登录判断发布时间:2022-07-13
下一篇:
[Swift]LeetCode323.无向图中的连通区域的个数$NumberofConnectedComponentsinanUndir ...发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap