加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

[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"; 
"dogcatsdog" can be concatenated by "dog","cats" and "dog";
"ratcatdogcat" can be concatenated by "rat","cat","dog" and "cat".?

Note:

  1. The number of elements of the given array will not exceed?10,000
  2. The length sum of elements in the given array will not exceed?600,000.
  3. All the input string will only include lower case letters.
  4. The returned elements order does not matter.

给定一个不含重复单词的列表,编写一个程序,返回给定单词列表中所有的连接词。

连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["cat","ratcatdogcat"]

输出: ["catsdogcats","ratcatdogcat"]

解释: "catsdogcats"由"cats","dog" 和 "cats"组成; 
     "dogcatsdog"由"dog","cats"和"dog"组成; 
     "ratcatdogcat"由"rat","dog"和"cat"组成。

说明:

  1. 给定数组的元素总数不超过?10000
  2. 给定数组中元素的长度总和不超过?600000
  3. 所有输入字符串只包含小写字母。
  4. 不需要考虑答案输出的顺序。

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 }

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读