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

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

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

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let s = Array(s)
        let t = Array(t)
        var r = Array(repeating:0, count: t.count)
        let dict = t.enumerated().reduce(into: [Character: [Int]]()) { $0[$1.1, default:[]].append($1.0) }
        for i in 0..<s.count {
            guard let indices = dict[s[i]] else { continue }
            for j in indices.reversed() {
                if j == 0 {
                    r[0] += 1
                } else {
                    r[j] += r[j-1]
                }
            }
        }
        return r[r.count-1]
    }
}

---

36ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        if s.isEmpty {return 0}
        let len:Int = s.count
        var dp:[Int] = [Int](repeating:1,count:len)
        var pre:Int,temp:Int
        let arrS:[Character] = Array(s)
        let arrT:[Character] = Array(t)
        for i in 0..<t.count
        {
            pre = dp[0]
            dp[0] = (i == 0 && arrS[0] == arrT[0]) ? 1 : 0
            for k in 1..<len
            {
                temp = dp[k]
                dp[k] = dp[k - 1] + (arrS[k] == arrT[i] ? pre : 0)
                pre = temp
            }
        }
        return dp[len - 1]
    }
}

---

68ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        if t.isEmpty { return 1 }
        if s.isEmpty || t.isEmpty { return 0 }
        var dp = Array(repeating: Array(repeating: 0, count: s.count + 1), count: t.count + 1)
        let arrS = Array(s)
        let arrT = Array(t)
        
        dp[0][0] = 1
        
        for i in 0...t.count {
            for j in 1...s.count {
                if i == 0 {
                    dp[0][j] = 1
                } else if arrS[j - 1] == arrT[i - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
                } else {
                    dp[i][j] = dp[i][j - 1]
                }
            }
        }

        return dp[t.count][s.count]
    }
}

---

72ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        return numDistinctDP(s, t)
    }
    
    func numDistinctDP(_ s: String, _ t: String) -> Int {
        guard !s.isEmpty else { return 0 }
        
        var sArray = Array(s)
        var tArray = Array(t)
        var matrix = Array(repeating: Array(repeating: 0, count: s.count + 1), 
                           count: t.count + 1)
        
        for i in 0...s.count {
            matrix[0][i] = 1
        }
        
        for i in 1...t.count {
            for j in 1...s.count {
                
                if tArray[i-1] == sArray[j-1] {
                    matrix[i][j] = matrix[i][j-1] + matrix[i-1][j-1]
                } else {
                    matrix[i][j] = matrix[i][j-1]
                }
                
            }
        }
        
        return matrix[t.count][s.count]
    }
    
    func isSubsequenceIteration(_ s: String, _ t: String) -> Bool {
        guard !s.isEmpty else { return true }
        guard !t.isEmpty else { return false }
        
        let sArray = Array(s)
        let tArray = Array(t)
        var current = 0
        
        for character in tArray {
            if sArray[current] == character {
                current += 1
                if current == sArray.count {
                    return true
                }
            }
        }
        
        return false
    }
}

---

96ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        if s.isEmpty || t.isEmpty {
            return 0
        }
        
        let rowCount = t.count
        let colCount = s.count
        let row = [Int](repeating: 0, count: colCount + 1)
        var matrix = [[Int]](repeating: row, count: rowCount + 1)
        matrix[0][0] = 1
        for i in 1..<colCount+1 {
            matrix[0][i] = 1
        }
        
        var i = 1
        for tChar in t {
            var j = 1
            for sChar in s {
                if sChar == tChar {
                    matrix[i][j] = matrix[i - 1][j - 1] + matrix[i][j - 1]
                } else {
                    matrix[i][j] = matrix[i][j - 1]
                }
                j += 1
            }
            i += 1
        }
        
        return matrix[rowCount][colCount]
    }
}

---

164ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        var mem = [[Int]]()
        for index in 0...t.count {
            if index == 0 {
                mem.append(Array(repeating: 1, count: s.count+1))
            } else {
                mem.append(Array(repeating: 0, count: s.count+1))
            }
        }
        
        for (i, tChar) in t.enumerated() {
            for (j, sChar) in s.enumerated() {
                if tChar == sChar {
                    mem[i+1][j+1] = mem[i][j] + mem[i+1][j]
                } else {
                    mem[i+1][j+1] = mem[i+1][j]
                }
            }
        }
        
        return mem[t.count][s.count]
    }
}

---

260ms

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        
        var dict:Dictionary<Character, [Int]> = Dictionary<Character, [Int]>()
        
        for (index, curChar) in s.enumerated() {
            var curIndexes = dict[curChar]
            if (curIndexes == nil) {
                curIndexes = []
                dict[curChar] = curIndexes
            }
            if var curIndexes = curIndexes {
                curIndexes.append(index)
                dict[curChar] = curIndexes
            }
        }
        
        var memo:Dictionary<String, Int> = Dictionary<String, Int>()
        //for each char in s, find t[0] = index
        //for each char in s find t[1] = index1
        return findNextIndex(dict, Array(t), 0, 0, &memo)        
    }
    
    func findNextIndex(_ dict:Dictionary<Character, [Int]>, _ t:[Character],_ curIndexChar:Int, _ curIndexString:Int,_ memo:inout Dictionary<String,Int>) -> Int {
        
        if (curIndexChar >= t.count) {
            return 1
        }
        
        let memKey = String(curIndexChar) + String(t) + String(curIndexString)
        if let precomputedRet =  memo[memKey] {
            return precomputedRet
        }
        
        var ret = 0
        
        let curChar = t[curIndexChar]
        if let indexes = dict[curChar] {
            for i in indexes {
                if (i >= curIndexString) {
                    ret += findNextIndex(dict, t, curIndexChar+1, i+1, &memo)
                }
            }
        }
        memo[memKey] = ret
        return ret
    }
}