Blog

leetcode115不同的子序列

leetcode115 Distinct Subsequences

Posted by BY on January 13, 2019

前言

新的一年，好好学习

正文

问题来源

本问题来自leetcode上的115题。虽然独立刷出，但感觉并不容易

问题描述

给定一个字符串 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
    ^^^

分析：

因为这题有动态规划这个提示，我们用表的形式填写，尝试写出递推公式。 S = “rabbbit”, T = “rabbit”

    r a b g b a a
  0 0 0 0 0 0 0 0
r 0 1 0 0 0 0 0 0
a 0 + 1 0 0 0 0 0
b 0 + + 1 2 3 0 0
b 0 + + + 1 3 0 0
i 0 + + + + 0 3 0
t 0 + + + + + 0 3

子序列S不可能长过序列T,表中+代表不可能，值等于0

S = “babgbag”, T = “bag”

    b a b g b a g
  0 0 0 0 0 0 0 0
b 0 1 0 2 0 3 0 0
a 0 + 1 0 0 0 4 0
g 0 + + 0 1 0 0 5

所以我们可以得到递推公式为：当T[i]==S[j]时（其中i,j为记录dp动态结果二维数组的行列标），上一行最接近j的非0值和本行最接近j的非0值之和。而当i=1（序列第一个）时，T[0]==T[j]，依次1,2,3…

本人写的Go代码如下：

func numDistinct(s string, t string) int {
    ls := len(s)
    lt := len(t)
    if ls < lt {
        return 0
    }
    dp := make([][]int, lt)
    for i := 0; i < lt; i++ {
        dp[i] = make([]int, ls)
    } 
    rawCount := 0
    for j := 0; j < ls; j++ {
        if t[0] == s[j] {
            rawCount++
            dp[0][j] = rawCount
        }
    }
    for i := 1; i < lt; i++ {
        rawCount = 0
        for j := i; j < ls; j++ {
            if t[i] == s[j] {
                lastCount := 0
                lastIndex := i-1
                for k := j-1; k >=lastIndex; k-- {
                    if dp[lastIndex][k] != 0 {
                        lastCount = dp[lastIndex][k]
                        break
                    }
                }
                rawCount += lastCount
                dp[i][j] = rawCount
            }
        }
    }
    return rawCount
}

经过研究发现，这并不是最优的。需要将表里的等于0的空间利用，减少时间开销。 S = “rabbbit”, T = “rabbit”

    r a b g b a a
  1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 + 1 1 1 1 1 1
b 0 + + 1 2 3 3 3
b 0 + + + 1 3 3 3
i 0 + + + + 0 3 3
t 0 + + + + + 0 3

子序列S不可能长过序列T,表中+代表不可能，值等于0

S = “babgbag”, T = “bag”

    b a b g b a g
  1 1 1 1 1 1 1 1
b 0 1 1 2 2 3 3 3
a 0 + 1 1 1 1 4 4
g 0 + + 0 1 1 1 5

这样省去了寻找上一行最接近j的非0值这个循环。 dp[i][j]表示T的从0开始长度为i的子串和S的从0开始长度为j的子串的匹配的个数。

比如, dp[2][3]表示T中的ra和S中的rab的匹配情况。

(1)显然，至少有dp[i][j] = dp[i][j - 1].   比如, 因为T 中的”ra” 匹配S中的 “ra”， 所以dp[2][2] = 1 。 显然T 中的”ra” 也匹配S中的 “rab”，所以s[2][3] 至少可以等于dp[2][2]。
(2) 如果T[i-1] == S[j-1]， 那么dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)；
比如, T中的”rab”和S中的”rab”显然匹配，
根据(1)， T中的”rab”显然匹配S中的“rabb”，所以dp[3][4] = dp[3][3] = 1，
根据(2),   T中的”rab”中的b等于S中的”rab1b2”中的b2, 所以要把T中的”rab”和S中的”rab1”的匹配个数累加到当前的dp[3][4]中。 所以dp[3][4] += dp[2][3] = 2; (3) 初始情况是 dp[0][0] = 1; // T和S都是空串.
dp[0][1 … S.length() ] = 1; // T是空串，S只有一种子序列匹配。
dp[1 … T.length() ][0] = 0; // S是空串，T不是空串，S没有子序列匹配。

func numDistinct(s string, t string) int {
    ls := len(s)
    lt := len(t)
    if ls < lt {
        return 0
    }
    dp := make([][]int, lt+1)
    for i := 0; i <= lt; i++ {
        dp[i] = make([]int, ls+1)
    } 
    for j := 0; j <= ls; j++ {
        dp[0][j] = 1
    }
    for i := 1; i <= lt; i++ {
        for j := i; j <= ls; j++ {
	    dp[i][j] = dp[i][j-1]
            if t[i-1] == s[j-1] {
                dp[i][j] += dp[i-1][j-1]
            }
        }
    }
    //fmt.Println(dp)
    return dp[lt][ls]
}

总结：

勤思考

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog