一、问题描述

给定字符串 s 和 t，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 进阶： 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

二、方案一：双指针法

1、思路

我们可以使用双指针的方法来解决这个问题。一个指针指向字符串 s，另一个指针指向字符串 t。遍历字符串 t，如果当前字符与 s 中的字符相同，则移动 s 的指针。如果 s 的指针移动到了 s 的末尾，说明 s 是 t 的子序列。

2、代码实现

func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 t 的长度。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间。

三、方案二：动态规划

1、思路

对于进阶问题，如果有大量输入的 S，我们可以使用动态规划来优化。我们可以创建一个二维数组 dp，其中 dp[i][j] 表示字符串 t 中从位置 i 开始的子串是否包含字符串 s 中从位置 j 开始的子串。这样，我们只需要预处理一次字符串 t，就可以快速判断大量的字符串 s 是否为 t 的子序列。

2、代码实现

func isSubsequence(s string, t string) bool {
    dp := make([][]bool, len(t) + 1)
    for i := range dp {
        dp[i] = make([]bool, len(s) + 1)
    }
    for i := 0; i <= len(t); i++ {
        dp[i][len(s)] = true
    }
    for i := len(t) - 1; i >= 0; i-- {
        for j := len(s) - 1; j >= 0; j-- {
            if t[i] == s[j] {
                dp[i][j] = dp[i+1][j+1]
            } else {
                dp[i][j] = dp[i+1][j]
            }
        }
    }
    return dp[0][0]
}

3、复杂度分析

• 时间复杂度：O(m*n)，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。
• 空间复杂度：O(m*n)，我们需要一个二维数组来存储动态规划的结果。

四、总结

方案	时间复杂度	空间复杂度	适用场景
双指针法	O(n)	O(1)	单次查询
动态规划	O(m*n)	O(m*n)	大量查询，预处理字符串 t

对于单次查询，双指针法是更优的选择，因为它的时间复杂度和空间复杂度都更低。对于大量查询的情况，动态规划是更好的选择，因为它可以通过预处理来加速查询。