题目

LeetCode.392.判断子序列（简单）

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

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

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

题解

解法1：双指针

可以直接拿s和t做比较，遇到不相同的字符就跳过，只要保证s所有字符在t中，并且顺序没有改变即可。

时间复杂度O(m + n)：m为字符串s长度，n为字符串t长度，最坏情况下两个指针都要移动到字符串末尾。
空间复杂度O(1)：没有额外空间占用。

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        var i = 0
        var j = 0
        while (i < s.length && j < t.length) {
            if (s[i] == t[j]) i++
            j++
        }
        return i == s.length
    }
}

解法2：后续挑战 - 动态规划

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。

双指针的问题在于：
S中的一个字符跟T中的字符匹配后，再去匹配下一个字符，需要在T中顺序查找，如果能直接查表得到位置，时间就降下来了。
假设S的长度为m，那么复杂度就可以降低为O(m)。

可以对T做预处理，记录位于T中第i个位置时字符j第一次出现的索引位置，用dp[i][j]来表示。
字符集是常数个，所以j的取值范围是一个常量。

状态转移方程
因为dp[i][j]记录的是j在i或i之后第一次出现的位置；
如果T[i] == j，dp[i][j] = i。
如果T[i] != j，dp[i][j] = dp[i + 1][j]。
如果i之后不存在字符j，令dp[i][j] = -1
要从后往前递推。

复杂度
设m为S长度，n为T长度。
预处理时间复杂度O(n)。
判断子序列时间复杂度O(m)。

空间复杂度O(n * 字符集个数)。

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        if (s.isEmpty()) return true
        if (t.isEmpty()) return false

        val m = s.length
        val n = t.length

        // 预处理
        val dp = Array(n) { IntArray(26) { -1 } }
        for (i in n - 1 downTo 0) {
            for (j in 0 until 26) {
                val c = ('a'.toInt() + j).toChar()
                if (t[i] == c) dp[i][j] = i
                else if (i < n - 1) dp[i][j] = dp[i + 1][j]
            }
        }

        var indexT = 0
        for (c in s) {
            // t已经没有后续字符了，s还没匹配完，那肯定不是子序列
            if (indexT == n) return false
            val cIndex = c.toInt() - 'a'.toInt()
            if (dp[indexT][cIndex] == -1) return false
            // s中的字符c匹配到了T中的字符，从T中下一个字符开始继续匹配
            indexT = dp[indexT][cIndex] + 1
        }
        
		return true
    }
}