判断子序列

概述：给定字符串


s


和


t


，判断


s


是否为


t


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


“ace”


是


“abcde”


的一个子序列，而


“aec”


不是）。

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

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

方法一：弹栈

思路：简化思路，把


t


遍历到新栈中进行判断，若不等于


s


顺序元素，则弹出。最后加上边界条件，返回判断即可。

# 弹栈
# 简化思路，把 t 遍历到新栈中进行判断，若不等于 s 顺序元素，则弹出。
# 最后加上边界条件，返回判断即可。
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        ans = []
        target = 0
        for i in range(len(t)):
            ans.append(t[i])
            if ans[-1] != s[target]:
                ans.pop()
            else:
                target += 1
            if len(ans) == len(s):
                break
        return ''.join(ans) == s

方法二：快慢指针

思路：此算法优势在于不借助空间存储，快指针指向全序列，慢指针指向子序列。依次循环判断即可。

# 快慢指针
# 此算法优势在于不借助空间存储，快指针指向全序列，慢指针指向子序列。
# 依次循环判断即可。
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        slow, fast = 0, 0
        while slow < len(s) and fast < len(t):
            if s[slow] == t[fast]:
                slow += 1
            fast += 1
        return slow == len(s)

方法三：动态规划

思路：


DP


比较难想，核心在于状态转移，依次循环判断即可。

# 动态规划
# DP 比较难想，核心在于状态转移，依次循环判断即可。
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        f = [[0] * 26 for _ in range(m)]
        f.append([m] * 26)
        for i in range(m - 1, -1, -1):
            for j in range(26):
                f[i][j] = i if ord(t[i]) == j + ord('a') else f[i + 1][j]
        add = 0
        for i in range(n):
            if f[add][ord(s[i]) - ord('a')] == m:
                return False
            add = f[add][ord(s[i]) - ord('a')] + 1
        return True

总结

我悟了，这就把ID改成“万物DP”！