[Swift]LeetCode720.词典中最长的单词|LongestWordinDictionary

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

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

示例 1:

输入: 
words = ["w","wo","wor","worl", "world"]
输出: "world"
解释: 
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

示例 2:

输入: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出: "apple"
解释: 
"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。

注意:

所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。

188ms

 1 class Solution {
 2     func longestWord(_ words: [String]) -> String {
 3     var result = ""
 4         let hashSet = Set(words)
 5         for word in words {
 6             var valid = true
 7             if word.count < result.count {
 8                 continue
 9             }
10             if word.count == result.count && word > result {
11                 continue
12             }
13             let startIndex = word.startIndex
14             for i in 0 ..< word.count - 1 {
15                 let index = word.index(startIndex, offsetBy: i+1)
16                 let mySubstring = word[..<index] // Hello
17                 if !hashSet.contains(String(mySubstring)) {
18                     valid = false
19                     break
20                 }
21             }
22             if valid {
23                 result = word
24             }
25         }
26         
27         return result
28     }
29 }

Runtime: 192 ms

Memory Usage: 20.2 MB

 1 class Solution {
 2     func longestWord(_ words: [String]) -> String {
 3         var res:String = String()
 4         var s:Set<String> = Set<String>()
 5         var words = words.sorted(by:<)
 6         for word in words
 7         {
 8             if word.count == 1 || s.contains(word.subString(0, word.count - 1))
 9             {
10                 res = (word.count > res.count) ? word : res
11                 s.insert(word)
12             }
13         }
14         return res
15     }
16 }
17 
18 extension String {
19     // 截取字符串：指定索引和字符数
20     // - begin: 开始截取处索引
21     // - count: 截取的字符数量
22     func subString(_ begin:Int,_ count:Int) -> String {
23         let start = self.index(self.startIndex, offsetBy: max(0, begin))
24         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
25         return String(self[start..<end]) 
26     }    
27 }

Runtime: 200 ms

Memory Usage: 20.5 MB

 1 class Solution {
 2     func longestWord(_ words: [String]) -> String {
 3         let sortedWords = words.sorted()
 4         var set = Set([""])
 5         var res = ""
 6 
 7         for word in sortedWords {
 8             if set.contains(String(word.prefix(word.count-1))) {
 9                 set.insert(word)
10                 if word.count > res.count {
11                     res = word
12                 }
13             }
14         }
15         return res
16     }
17 }

208ms

 1 class Solution {    
 2     enum Contains {        
 3         case unknown
 4         case valid
 5         case invalid        
 6     }    
 7     
 8     func longestWord(_ words: [String]) -> String {
 9 
10         var max = 0
11         var maxString = ""
12         var hash = [String: Contains]()
13         
14         for eachWord in words {            
15             if eachWord.count == 1 {
16                 hash[eachWord] = .valid
17                 max = 1
18                 maxString = eachWord
19                 continue
20             }            
21             hash[eachWord] = .unknown
22         }
23         for eachWord in words {
24             
25             if eachWord.count >= max && isValid(eachWord, in: &hash) { 
26                 if eachWord.count == max && eachWord > maxString {
27                     continue
28                 }                  
29                 max = eachWord.count
30                 maxString = eachWord
31             }
32         } 
33         return maxString
34     }
35     
36     func isValid(_ word: String, in hash: inout [String: Contains] ) -> Bool {
37         guard word.count > 1 else { return true }
38         var stack = [String]()
39         
40         for i in (0..<word.count-1).reversed() {
41             let endIndex = word.index(word.startIndex, offsetBy:i)
42             let subWord = String(word[word.startIndex...endIndex])
43             
44             if let state = hash[subWord] {
45                 switch state {
46                     case .valid: 
47                         for each in stack {
48                             hash[each] = .valid
49                         }
50                         return true
51                     case .invalid: 
52                         for each in stack {
53                             hash[each] = .invalid
54                         }
55                         return false
56                     case .unknown: 
57                         stack.append(subWord)
58                 }
59             }
60             else {
61                 return false
62             }
63         }        
64         return false
65     }
66 }

216ms

 1 class Solution {
 2     func longestWord(_ words: [String]) -> String {
 3         var answer = ""
 4         var wordSet = Set<String>()
 5         let sortedWords = words.sorted()
 6         
 7         for word in sortedWords {
 8             if word.count == 1 || wordSet.contains(String(word.prefix(word.count-1))) {
 9                 answer = word.count > answer.count ? word : answer
10                 wordSet.insert(word)
11             }
12         }
13         return answer
14     }
15 }

224ms

 1 class Solution {
 2   func longestWord(_ words: [String]) -> String {
 3     let hash = Set(words)    
 4     // Mark all words that can be built from available words
 5     var longestWord = ""
 6     for word in hash {      
 7       guard word.count >= longestWord.count else { continue }
 8       if word.count == longestWord.count { guard word < longestWord else { continue } }            
 9       var trunc = word
10       var isValid = false
11       for _ in 0 ..< word.count {
12         if trunc.count == 1 { isValid = hash.contains(trunc); break }        
13         trunc = String(trunc.dropLast())
14         guard hash.contains(trunc) else { break }
15       }
16       guard isValid else { continue }
17       longestWord = word
18     }    
19     return longestWord
20   }
21 }