[Swift]LeetCode126.单词接龙II|WordLadderII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 all shortest transformation sequence(s) 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.

Note:

Return an empty list 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:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

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

说明:

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

示例 1:

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

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

3640ms

 1 class Solution {
 2     let alphabet = Array("abcdefghijklmnopqrstuvwxyz")
 3 
 4     func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
 5         var dictionary = Set(wordList)
 6         var result = [[String]]()
 7         var distance = [String: Int]()
 8         var neighbors = [String: [String]]()
 9 
10         dictionary.insert(beginWord)
11 
12         // Get distances and neighbors for each word
13         bfs(beginWord, endWord, &dictionary, &distance, &neighbors)
14 
15         // Get results of word ledders
16         var temp = [String]()
17         dfs(beginWord, endWord, &dictionary, &distance, &neighbors, &result, &temp)
18 
19         return result
20     }
21 
22     private func bfs(_ beginWord: String, _ endWord: String, _ dictionary: inout Set<String>, _ distance: inout [String: Int], _ neighbors: inout [String: [String]]) {
23         for word in dictionary {
24             neighbors[word] = [String]()
25         }
26 
27         var queue = [String]()
28         queue.append(beginWord)
29         distance[beginWord] = 0
30 
31         while !queue.isEmpty {
32             var newQueue = [String]()
33             var foundEnd = false
34             for word in queue {
35                 let wordDistance = distance[word]!
36                 let wordNeighbors = getNeighbors(&dictionary, word)
37                 for neighbor in wordNeighbors {
38                     neighbors[word]!.append(neighbor)
39                     if distance[neighbor] == nil {
40                         distance[neighbor] = wordDistance + 1
41                         if neighbor == endWord {
42                             foundEnd = true
43                         } else {
44                             newQueue.append(neighbor)
45                         }
46                     }
47                 }
48             }
49             if foundEnd {
50                 break
51             }
52             queue = newQueue
53         }
54     }
55 
56     private func getNeighbors(_ dictionary: inout Set<String>, _ word: String) -> [String] {
57         var wordChars = Array(word)
58         var result = [String]()
59         for i in 0..<word.count {
60             let oldChar = wordChars[i]
61             for letter in alphabet {
62                 wordChars[i] = letter
63                 let newWord = String(wordChars)
64                 if dictionary.contains(newWord) {
65                     result.append(newWord)
66                 }
67             }
68             wordChars[i] = oldChar
69         }
70         return result
71     }
72 
73     private func dfs(_ beginWord: String, _ endWord: String, _ dictionary: inout Set<String>, _ distance: inout [String: Int], _ neighbors: inout [String: [String]], _ result: inout [[String]], _ temp: inout [String]) {
74         temp.append(beginWord)
75         if beginWord == endWord {
76             result.append(temp)
77         } else {
78             let wordDistance = distance[beginWord]!
79             for neighbor in neighbors[beginWord]! {
80                 if distance[neighbor]! == wordDistance + 1 {
81                     dfs(neighbor, endWord, &dictionary, &distance, &neighbors, &result, &temp)
82                 }
83             }
84         }
85         temp.removeLast()
86     }
87 }

4284ms

 1 class Solution {
 2     func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
 3         var res:[[String]] = [[String]]()
 4          //加速查找
 5         var dict:Set<String> = Set<String>(wordList)
 6         //构建队列
 7         var p:[String] = [String]()
 8         //加入源顶点
 9         p.append(beginWord)
10         var paths:[[String]] = [[String]]()
11         paths.append(p)
12         var level:Int = 1, minLevel:Int = Int.max
13         var words:Set<String> = Set<String>()
14         while (paths.count != 0)
15         {
16             var t = paths.removeFirst()
17             if t.count > level
18             {
19                 for w in words{dict.remove(w)}
20                 words = Set<String>()
21                 level = t.count
22                 if level > minLevel {break}
23             }
24             var last:String = t.last!
25             for i in 0..<last.count
26             {
27                 var newLast:String = last
28                 for ch in 97...122
29                 {
30                     newLast[i] = ch.ASCII
31                     if !dict.contains(newLast){continue}
32                     words.insert(newLast)
33                     var nextPath = t
34                     nextPath.append(newLast)
35                     if newLast == endWord
36                     {
37                         res.append(nextPath)
38                         minLevel = level
39                     }
40                     else
41                     {
42                         paths.append(nextPath)
43                     }
44                 }
45             }
46         }
47         return res
48     }
49 }
50 
51 //String扩展方法
52 extension String {
53     func toCharArray() -> [Character]
54     {
55         var arr:[Character] = [Character]()
56         for char in self.characters
57         {
58             arr.append(char)
59         }
60         return arr
61     }
62     
63     //subscript函数可以检索数组中的值
64     //直接按照索引方式截取指定索引的字符
65     subscript (_ i: Int) -> Character {
66         //读取字符
67         get {return self[index(startIndex, offsetBy: i)]}
68         
69         //修改字符
70         set
71         {
72             var str:String = self
73             var index = str.index(startIndex, offsetBy: i)
74             str.remove(at: index)
75             str.insert(newValue, at: index)
76             self = str
77         }
78     }
79 }
80 
81 //Int扩展方法  
82 extension Int
83 {
84     //属性：ASCII值(定义大写为字符值)
85     var ASCII:Character 
86     {
87         get {return Character(UnicodeScalar(self)!)}
88     }
89 }