• 【算法题解记录】_1
  • leetcode_115题

【算法题解记录】_1

还是干这个事了，要吃饭嘛，决定把在解题或者解完题进一步优化的时候，发现的有意思的地方记录一下

leetcode_115题

动态规划解的字符串匹配，矩阵全部都遍历，用时比较长，发现排在网友们的末尾

纸上画了一下矩阵，行数代表被匹配串s，列数代表匹配串t，右上角和左下角是不需要计算的

因为右上角恒为0，左下角对结果无贡献

代码修改为：

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        lens = len(s)
        lent = len(t)
        s = " " + s
        t = " " + t
        f = [[0]*(lent+1) for _ in range(lens+1)]
        for i in range(lens+1):
            f[i][0] = 1
        for i in range(1,lens+1):
            for j in range(1,lent+1):
                if i > j + (lens - lent): continue
                if i < j: break
                f[i][j] = f[i-1][j]
                if s[i] == t[j]:
                    f[i][j] += f[i-1][j-1]
        return f[lens][lent]

好像不论哪种情况，都是只能一种break另一种continue，因为遍历的增长方向是逐行或逐列按一个方向增长的

结果用时是