[Swift]LeetCode472. 连接词 | Concatenated Words
发布时间:2020-12-14 05:04:44 所属栏目:百科 来源:网络整理
导读:Given a list of words (without duplicates),please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the gi
Given a list of words (without duplicates),please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. Example: Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats","dog" and "cats"; Note:
给定一个不含重复单词的列表,编写一个程序,返回给定单词列表中所有的连接词。 连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。 示例: 输入: ["cat","ratcatdogcat"] 输出: ["catsdogcats","ratcatdogcat"] 解释: "catsdogcats"由"cats","dog" 和 "cats"组成; "dogcatsdog"由"dog","cats"和"dog"组成; "ratcatdogcat"由"rat","dog"和"cat"组成。 说明:
Runtime:?8332 ms
Memory Usage:?10.2 MB
1 class Solution { 2 func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] { 3 var res:[String] = [String]() 4 var dict:Set<String> = Set(words) 5 for word in words 6 { 7 var n:Int = word.count 8 if n == 0 {continue} 9 var dp:[Bool] = [Bool](repeating:false,count:n + 1) 10 dp[0] = true 11 for i in 0..<n 12 { 13 if !dp[i] {continue} 14 for j in (i + 1)...n 15 { 16 var str:String = word.subString(i,j - i) 17 if j - i < n && dict.contains(str) 18 { 19 dp[j] = true 20 } 21 } 22 if dp[n] 23 { 24 res.append(word) 25 break 26 } 27 } 28 } 29 return res 30 } 31 } 32 33 extension String { 34 // 截取字符串:指定索引和字符数 35 // - begin: 开始截取处索引 36 // - count: 截取的字符数量 37 func subString(_ begin:Int,_ count:Int) -> String { 38 let start = self.index(self.startIndex,offsetBy: max(0,begin)) 39 let end = self.index(self.startIndex,offsetBy: min(self.count,begin + count)) 40 return String(self[start..<end]) 41 } 42 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |