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

[Swift]LeetCode522.最长特殊序列II|LongestUncommonSubsequenceII

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

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

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

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

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

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.

Example 1:

Input: "aba", "cdc", "eae"
Output: 3 

Note:

  1. All the given strings' lengths will not exceed 10.
  2. The length of the given list will be in the range of [2, 50].

给定字符串列表,你需要从它们中找出最长的特殊序列。最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。

子序列可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。

输入将是一个字符串列表,输出是最长特殊序列的长度。如果最长特殊序列不存在,返回 -1 。 

示例:

输入: "aba", "cdc", "eae"
输出: 3 

提示:

  1. 所有给定的字符串长度不会超过 10 。
  2. 给定字符串列表的长度将在 [2, 50 ] 之间。

Runtime: 16 ms
Memory Usage: 19.8 MB
 1 class Solution {
 2     func findLUSlength(_ strs: [String]) -> Int {
 3         var strs = strs
 4         var n:Int = strs.count
 5         var s:Set<String> = Set<String>()
 6         strs.sort(by:{
 7             if $0.count == $1.count
 8             {
 9                 return $0 > $1
10             }
11              return $0.count > $1.count
12         })
13         for i in 0..<n
14         {
15             if i == n - 1 || strs[i] != strs[i + 1]
16             {
17                 var found:Bool = true
18                 for a in s
19                 {
20                     var j:Int = 0
21                     for c in a.characters
22                     {
23                         if c == strs[i][j] {j += 1}
24                         if j == strs[i].count {break}
25                     }
26                     if j == strs[i].count
27                     {
28                         found = false
29                         break
30                     }
31                 }
32                 if found {return strs[i].count}                
33             }
34             s.insert(strs[i])
35         }
36         return -1
37     }
38 }
39 
40 extension String {        
41     //subscript函数可以检索数组中的值
42     //直接按照索引方式截取指定索引的字符
43     subscript (_ i: Int) -> Character {
44         //读取字符
45         get {return self[index(startIndex, offsetBy: i)]}
46     }
47 }

16ms

 1 class Solution {
 2     func findLUSlength(_ strs: [String]) -> Int {
 3         var sortStrs = strs.sorted { 
 4             return $1.count < $0.count || ($1.count == $0.count && $1 < $0 )
 5         }
 6         let duplicates = getDuplicates(sortStrs)
 7         for i in sortStrs.indices {
 8             if !duplicates.contains(sortStrs[i]) {
 9                 if i == 0 { return sortStrs[i].count }
10                 for j in 0..<i {
11                     if isSubsequence(Array(sortStrs[j]), Array(sortStrs[i])) {
12                         break
13                     }
14                     if j == i-1 {
15                         return sortStrs[i].count
16                     }
17                 }
18             }
19         }
20         return -1
21     }
22 
23     func isSubsequence(_ chars1: [Character], _ chars2: [Character]) -> Bool {
24         var i = 0, j = 0
25         while i<chars1.count && j<chars2.count {
26             if chars1[i] == chars2[j] {
27                 j += 1
28             }
29             i += 1
30         }
31         return j == chars2.count
32     }
33 
34     func getDuplicates(_ strs: [String]) -> Set<String> {
35         var set = Set<String>()
36         var duplicates = Set<String>()
37         for s in strs {
38             if set.contains(s) {
39                 duplicates.insert(s)
40             }else {
41                 set.insert(s)
42             }
43         }
44         return duplicates
45     }
46 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Project Perfect让Swift在服务器端跑起来-引言(一)发布时间:2022-07-13
下一篇:
swift泛型发布时间: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