[Swift]LeetCode115.不同的子序列|DistinctSubsequences

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

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

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

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

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

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

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

示例 1:

输入: S = "rabbbit", T = "rabbit"
输出: 3
解释:

如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2:

输入: S = "babgbag", T = "bag"
输出: 5
解释:

如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

8ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         let s = Array(s)
 4         let t = Array(t)
 5         var r = Array(repeating:0, count: t.count)
 6         let dict = t.enumerated().reduce(into: [Character: [Int]]()) { $0[$1.1, default:[]].append($1.0) }
 7         for i in 0..<s.count {
 8             guard let indices = dict[s[i]] else { continue }
 9             for j in indices.reversed() {
10                 if j == 0 {
11                     r[0] += 1
12                 } else {
13                     r[j] += r[j-1]
14                 }
15             }
16         }
17         return r[r.count-1]
18     }
19 }

36ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         if s.isEmpty {return 0}
 4         let len:Int = s.count
 5         var dp:[Int] = [Int](repeating:1,count:len)
 6         var pre:Int,temp:Int
 7         let arrS:[Character] = Array(s)
 8         let arrT:[Character] = Array(t)
 9         for i in 0..<t.count
10         {
11             pre = dp[0]
12             dp[0] = (i == 0 && arrS[0] == arrT[0]) ? 1 : 0
13             for k in 1..<len
14             {
15                 temp = dp[k]
16                 dp[k] = dp[k - 1] + (arrS[k] == arrT[i] ? pre : 0)
17                 pre = temp
18             }
19         }
20         return dp[len - 1]
21     }
22 }

68ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         if t.isEmpty { return 1 }
 4         if s.isEmpty || t.isEmpty { return 0 }
 5         var dp = Array(repeating: Array(repeating: 0, count: s.count + 1), count: t.count + 1)
 6         let arrS = Array(s)
 7         let arrT = Array(t)
 8         
 9         dp[0][0] = 1
10         
11         for i in 0...t.count {
12             for j in 1...s.count {
13                 if i == 0 {
14                     dp[0][j] = 1
15                 } else if arrS[j - 1] == arrT[i - 1] {
16                     dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
17                 } else {
18                     dp[i][j] = dp[i][j - 1]
19                 }
20             }
21         }
22 
23         return dp[t.count][s.count]
24     }
25 }

72ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         return numDistinctDP(s, t)
 4     }
 5     
 6     func numDistinctDP(_ s: String, _ t: String) -> Int {
 7         guard !s.isEmpty else { return 0 }
 8         
 9         var sArray = Array(s)
10         var tArray = Array(t)
11         var matrix = Array(repeating: Array(repeating: 0, count: s.count + 1), 
12                            count: t.count + 1)
13         
14         for i in 0...s.count {
15             matrix[0][i] = 1
16         }
17         
18         for i in 1...t.count {
19             for j in 1...s.count {
20                 
21                 if tArray[i-1] == sArray[j-1] {
22                     matrix[i][j] = matrix[i][j-1] + matrix[i-1][j-1]
23                 } else {
24                     matrix[i][j] = matrix[i][j-1]
25                 }
26                 
27             }
28         }
29         
30         return matrix[t.count][s.count]
31     }
32     
33     func isSubsequenceIteration(_ s: String, _ t: String) -> Bool {
34         guard !s.isEmpty else { return true }
35         guard !t.isEmpty else { return false }
36         
37         let sArray = Array(s)
38         let tArray = Array(t)
39         var current = 0
40         
41         for character in tArray {
42             if sArray[current] == character {
43                 current += 1
44                 if current == sArray.count {
45                     return true
46                 }
47             }
48         }
49         
50         return false
51     }
52 }

96ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         if s.isEmpty || t.isEmpty {
 4             return 0
 5         }
 6         
 7         let rowCount = t.count
 8         let colCount = s.count
 9         let row = [Int](repeating: 0, count: colCount + 1)
10         var matrix = [[Int]](repeating: row, count: rowCount + 1)
11         matrix[0][0] = 1
12         for i in 1..<colCount+1 {
13             matrix[0][i] = 1
14         }
15         
16         var i = 1
17         for tChar in t {
18             var j = 1
19             for sChar in s {
20                 if sChar == tChar {
21                     matrix[i][j] = matrix[i - 1][j - 1] + matrix[i][j - 1]
22                 } else {
23                     matrix[i][j] = matrix[i][j - 1]
24                 }
25                 j += 1
26             }
27             i += 1
28         }
29         
30         return matrix[rowCount][colCount]
31     }
32 }

164ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         var mem = [[Int]]()
 4         for index in 0...t.count {
 5             if index == 0 {
 6                 mem.append(Array(repeating: 1, count: s.count+1))
 7             } else {
 8                 mem.append(Array(repeating: 0, count: s.count+1))
 9             }
10         }
11         
12         for (i, tChar) in t.enumerated() {
13             for (j, sChar) in s.enumerated() {
14                 if tChar == sChar {
15                     mem[i+1][j+1] = mem[i][j] + mem[i+1][j]
16                 } else {
17                     mem[i+1][j+1] = mem[i+1][j]
18                 }
19             }
20         }
21         
22         return mem[t.count][s.count]
23     }
24 }

260ms

 1 class Solution {
 2     func numDistinct(_ s: String, _ t: String) -> Int {
 3         
 4         var dict:Dictionary<Character, [Int]> = Dictionary<Character, [Int]>()
 5         
 6         for (index, curChar) in s.enumerated() {
 7             var curIndexes = dict[curChar]
 8             if (curIndexes == nil) {
 9                 curIndexes = []
10                 dict[curChar] = curIndexes
11             }
12             if var curIndexes = curIndexes {
13                 curIndexes.append(index)
14                 dict[curChar] = curIndexes
15             }
16         }
17         
18         var memo:Dictionary<String, Int> = Dictionary<String, Int>()
19         //for each char in s, find t[0] = index
20         //for each char in s find t[1] = index1
21         return findNextIndex(dict, Array(t), 0, 0, &memo)        
22     }
23     
24     func findNextIndex(_ dict:Dictionary<Character, [Int]>, _ t:[Character],_ curIndexChar:Int, _ curIndexString:Int,_ memo:inout Dictionary<String,Int>) -> Int {
25         
26         if (curIndexChar >= t.count) {
27             return 1
28         }
29         
30         let memKey = String(curIndexChar) + String(t) + String(curIndexString)
31         if let precomputedRet =  memo[memKey] {
32             return precomputedRet
33         }
34         
35         var ret = 0
36         
37         let curChar = t[curIndexChar]
38         if let indexes = dict[curChar] {
39             for i in indexes {
40                 if (i >= curIndexString) {
41                     ret += findNextIndex(dict, t, curIndexChar+1, i+1, &memo)
42                 }
43             }
44         }
45         memo[memKey] = ret
46         return ret
47     }
48 }