二、字符串（36）392. 判断子序列

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

我的题解：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        l1 = len(s)
        l2 = len(t)
        if l1 > l2:
            return False
        elif l1 == l2:
            if s == t:
                return True
            else:
                return False
        else:
            i = 0
            j = 0
            while  i < l1 and j < l2:
                if s[i] == t[j]:
                    i += 1
                j += 1

        if i == l1:
            return True
        else:
            return False

官方题解：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        i = j = 0
        while i < n and j < m:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == n

方法二：动态规划

思路及算法

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

一般这些子问题很相似，可以通过函数关系式递推出来。然后呢，动态规划就致力于解决每个子问题一次，减少重复计算,比如斐波那契数列就可以看做入门级的经典动态规划问题。

动态规划核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

• 递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。
• 动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从f(1)往f(10）方向，往上推求解，所以称为自底向上的解法。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:

'''
m表示该字符没有出现，每一行除了对应的行头的出现位置是本行外，行头之后的元素的第一次出现位置都是从下一行继承而来
'''

        n, m = len(s), len(t)#子串与串的长度
        #['Hi!'] * 4 =	['Hi!', 'Hi!', 'Hi!', 'Hi!']
        #[0] * 26 = [0,0,0,0,0,0,0,0,0,0,0,...,0] 26个0
        #[[0] * 26 for _ in range(m)] = [[0,...,0] , ..., [0,...,0]] m个[0,...,0]
        #构造一个二维矩阵，m行26列
        f = [[0] * 26 for _ in range(m)]# 初始化m个长度为26的列表记录字母a-z的位置
        #	list.append(obj) 在列表末尾添加新的对象
        #[[0,...,0] , ..., [0,...,0], [m,...,m]] m+1
        f.append([m] * 26)#补充，给f[m-1]行用，补充m表示未存在

        #range(5):0-4 range(5,9) :5-8 
        #range(m - 1, -1, -1): m-1 - 0
        #填充矩阵
        for i in range(m - 1, -1, -1):#从后往前m-1 —— 0
            for j in range(26):#从左往右
                # 记录字母a-z在t[i:]中的位置,如果第i个字符等于字符[a-z][j],那么j在i的位置,
                #否则j在t[i+1:]范围,这里倒序遍历,如果j不存在那么f[i][j]的值就是m
                #ord(t[i]) == j + ord('a') : 找到t[i]对应的元素，在该行（a-z）的位置
                #ord(t[i]) != j + ord('a')时  使用f[i + 1][j]的值进行覆盖
                #存放的是a-z 26个字母在t[i]开始之后的出现位置，不存在则记为m
                f[i][j] = i if ord(t[i]) == j + ord('a') else f[i + 1][j]

        #从第0行开始
        add = 0
        for i in range(n):#遍历子串s
            #ord(s[i]) - ord('a')表示s[i]对应的列 == m表示不存在
            if f[add][ord(s[i]) - ord('a')] == m:# 从t的第0个字符开始,如果f[0][j]==m,
                #也就是说字母j不在t内,返回false,[ord(s[i]) - ord('a')]表示j,也就是在f数组中
                #的位置
                return False
            #+ 1是因为f[add][ord(s[i]) - ord('a')]这个位置已经匹配了，从下一行开始
            add = f[add][ord(s[i]) - ord('a')] + 1
        #都在
        return True