判断子序列[简单]

优质博文：IT-BLOG-CN

一、题目

给定字符串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
两个字符串都只由小写字符组成。

二、代码

【1】双指针： 初始化两个指针i和j，分别指向s和t的初始位置。匹配成功则i和j同时右移，匹配s的下一个位置，匹配失败则j右移，i不变，尝试用t的下一个字符匹配s。最终如果i移动到s的末尾，就说明s是t的子序列。

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 定义两个双指针进行移动， 如果指针指向的位置相同，两个指针指向下一位，如果不相同，s指针移动一位
        int sIndex = 0, tIndex = 0;
        while (tIndex < t.length() && sIndex < s.length()) {
            if (t.charAt(tIndex) == s.charAt(sIndex)) {
                ++sIndex;
            }
            ++tIndex;
        }
        return sIndex == s.length();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度： O(n+m)其中n为s的长度，m为t的长度。每次无论是匹配成功还是失败，都有至少一个指针发生右移，两指针能够位移的总距离为n+m。
空间复杂度： O(1)。

【2】动态规划： 我们可以预处理出对于t的每一个位置，从该位置开始往后每一个字符第一次出现的位置。我们可以使用动态规划的方法实现预处理，令f[i][j]表示字符串t中从位置i开始往后字符j第一次出现的位置。在进行状态转移时，如果t中位置i的字符就是j，那么f[i][j]=i，否则j出现在位置i+1开始往后，即f[i][j]=f[i+1][j]，因此我们要倒过来进行动态规划，从后往前枚举i。

这样我们可以写出状态转移方程：

假定下标从0开始，那么f[i][j]中有0≤i≤m−1，对于边界状态f[m−1][..]，我们置f[m][..]为m，让f[m−1][..]正常进行转移。这样如果f[i][j]=m，则表示从位置i开始往后不存在字符j。

这样，我们可以利用f数组，每次O(1)地跳转到下一个位置，直到位置变为m或s中的每一个字符都匹配成功。

同时我们注意到，该解法中对t的处理与s无关，且预处理完成后，可以利用预处理数组的信息，线性地算出任意一个字符串s是否为t的子串。这样我们就可以解决「后续挑战」啦。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();

        int[][] f = new int[m + 1][26];
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {
                return false;
            }
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度： O(m×∣Σ∣+n)，其中n为s的长度，m为t的长度，Σ为字符集，在本题中字符串只包含小写字母，∣Σ∣=26。预处理时间复杂度O(m)，判断子序列时间复杂度O(n)。

如果是计算k个平均长度为n的字符串是否为t的子序列，则时间复杂度为O(m×∣Σ∣+k×n)。

空间复杂度： O(m×∣Σ∣)为动态规划数组的开销。