Leetcode: 115. Distinct Subsequences

Description

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).

It's guaranteed the answer fits on a 32-bit signed integer.

Example

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
^^^ ^^^

分析

Code

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        def oord(k):
            return ord(k)-96 if ord(k) > 91 else ord(k)-64
        
        helper, dp = [[] for i in range(26)], [0]*(len(t)+1)
        dp[0] = 1
        for k, v in enumerate(t):
            helper[oord(v)].append(k)
        s = ''.join([i for i in s if i in t])
        for i in s:
            for j in reversed(helper[oord(i)]):
                dp[j+1] += dp[j]
        return dp[-1]

总结

这是 2020 3 月份自己独立写出来的， 第二次就是 AC 了， 第一次是 runtime error。 提交后 3 月后发现 仍然了战胜了 99.71 % 的提交。不知道当时是否是战胜 100 % 的。

最最关键的时， 3 月后。我拿到了题目，居然无从下手。不像是二次 就 AC 的人啊。 难道学习不会增加实力？ 只是这边增加一点，那边少一点？
看了 几分钟后，发现思路还是挺 表意。没有任何奇技淫巧