[Swift]LeetCode940. 不同的子序列 II | Distinct Subsequences II - Swift 教程-OStack程序员社区-中国程序员成长平台

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

[Swift]LeetCode940. 不同的子序列 II | Distinct Subsequences II

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

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

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

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

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

Given a string S, count the number of distinct, non-empty subsequences of S .

Since the result may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

S contains only lowercase letters.
1 <= S.length <= 2000

给定一个字符串 S，计算 S 的不同非空子序列的个数。

因为结果可能很大，所以返回答案模 10^9 + 7.

示例 1：

输入："abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入："aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入："aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

S 只包含小写字母。
1 <= S.length <= 2000

28ms

 1 class Solution {
 2     func distinctSubseqII(_ S: String) -> Int {
 3         return distinctSubsequence(S.toCharArray(), 1000000007)
 4     }
 5     
 6     func distinctSubsequence(_ a:[Character],_ mod:Int) -> Int
 7     {
 8         var n = a.count
 9         var bucket:[Int] = [Int](repeating: -1,count: 26)
10         
11         var cum:Int = 0
12         for i in 0..<n
13         {
14             var v:Int = cum
15             //'a'的ASCII码值：97
16             var ind:Int = a[i].ascii - 97
17             if bucket[ind] == -1
18             {
19                 v += 1
20             }
21             else
22             {
23                 v += mod - bucket[ind]
24             }
25             if v >= mod
26             { 
27                 v -= mod
28             }
29             bucket[ind] = cum
30             cum += v
31             if cum >= mod
32             {
33                 cum -= mod
34             }
35         }
36         return cum
37     }
38 }
39 
40 //String扩展方法
41 extension String {
42     func toCharArray() -> [Character]
43     {
44         var arr:[Character] = [Character]()
45         for char in self.characters
46         {
47             arr.append(char)
48         }
49         return arr
50     }
51 }
52 
53 //Character扩展方法  
54 extension Character  
55 {  
56   //转ASCII整数值(定义小写为整数值)
57    var ascii: Int {
58         get {
59             let s = String(self).unicodeScalars
60             return Int(s[s.startIndex].value)
61         }
62     }
63 }