判断子序列

Leetcode Link: 392. 判断子序列 - 力扣（LeetCode）

题目

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

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

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

解法一

思路：俩指针遍历就完了

• 当 s[i] == t[j] 时，i++, j++
• 否则, j++

注意当 s == "" 的时候，无论 t 是什么，都返回 True

题解：

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

解法二

【不推荐】

从暴力递归到动态规划

暴力递归

典型的样本对应模型

样本对应模型的两个输入 i 和 j 分别表示两个样本的 [0…i] 和 [0 … j] 范围上的内容。

两种情况讨论

1. i, j是公共的子序列，有前提，需要相等
2. i可能不是公共子序列，只需要j动，i不动

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        @functools.lru_cache()
        def process(i, j):
            if i < 0:
                return True
            if j < 0:
                return False
 
            p1 = False
            if s[i] == t[j]:
                p1 = process(i-1, j-1)
            p2 = process(i, j-1)
            return p1 or p2
        
        if s == "":
            return True
        if t == "":
            return False
        return process(len(s)-1, len(t)-1)

动态规划

不是和暴力递归对应的

本题用dp写麻烦，难想，需要定义的是数量，最后要判断长度是不是相等，绕了一下，没必要。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s == "":
            return True
        if t == "":
            return False
        # [i, j]
        dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
 
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
        return True if dp[-1][-1] == len(s) else False

启发和联系