115. 不同的子序列 - Kotlin 二维字符串DP

原题地址：https://leetcode.cn/problems/distinct-subsequences/description/

题解

设dp[i][j]是子串s[0:i]和子串t[0:j]的匹配情况

当我们对子串s解析到字符s[i]时，不论是否有匹配，我们都可以选择跳过该字符，在这种情况下

以rabbbit和rabbit为例，当我们解析到rabbbit时，可以匹配rab，也可以跳过该字符仅匹配ra
边界情况：当i==0时，跳过该字符仍然没有任何匹配情况，因此dp[i][j]=0

当满足s[i]等于t中的某个字符t[j]时，若我们选择不跳过该字符，则对于该字符c而言：

子串s[0:i]和子串t[0:j]实际上是子串s[0:i-1]和子串t[0:j-1]各自加上该字符c而匹配的，此时在原本的情况（dp[i-1][j]）上还需加上dp[i-1][j-1]的情况

边界情况：当i==0或j==0时，为s或t中任意一者为空串，加一个字符匹配到另一子串，此时只有一种匹配情况，因此dp[i][j]+=1
考虑到一种特殊情况，当i<j时，是不可能匹配成功的，比如说rab是不可能匹配到rabb的，因此当i<j时应当不进行该操作

时间复杂度：O(MN)

空间复杂度：O(MN)

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val dp = Array(s.length) { Array(t.length) { 0 } }
        val map = HashMap<Char, ArrayList<Int>>()
        for ((index, char) in t.withIndex()) {
            if (!map.containsKey(char)) {
                map[char] = ArrayList()
            }
            map[char]!!.add(index)
        }
        for (i in s.indices) {
            //不匹配的情况下，继承i-1的情况
            for (j in t.indices) {
                dp[i][j] = if (i - 1 >= 0) dp[i - 1][j] else 0
            }
            if (map.containsKey(s[i])) {
                //匹配的情况，即子串[0:i-1]和[0:j-1]均加上一个字符s[i]匹配到子串[0:j]的情况
                for (j in map[s[i]]!!) {
                    dp[i][j] += if (i >= j) (if (i - 1 >= 0 && j - 1 >= 0) (dp[i - 1][j - 1]) else 1) else 0
                }
            }
        }
        return dp[s.length - 1][t.length - 1]
    }
}