26.判断子序列

题目

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

思路

首先，如果 s 是空串，直接返回 true，因为空串是任何字符串的子序列。
设置双指针 i , j 分别指向字符串 s , t 的首个字符，遍历字符串 t:

• 当 s[i] == t[j] 时，代表匹配成功，此时同时 i++ , j++ ；
  • 进而，若 i 已走过 s 尾部，代表 s 是 t 的子序列，此时应提前返回 true ；
• 当 s[i] != t[j] 时，代表匹配失败，此时仅 j++ ；

若遍历完字符串 t 后，字符串 s 仍未遍历完，代表 s 不是 t 的子序列，此时返回 false 。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        var sIndex = 0
        var tIndex = 0
        var sLength = s.length
        var tLength = t.length
        while(sIndex < sLength && tIndex < tLength) {
            if (s[sIndex] == t[tIndex]) {
                sIndex ++
            }
            tIndex ++
        }

        return sIndex == sLength
    }
}

复杂度分析:

• 时间复杂度 O(N) ： 其中 N 为字符串 t 的长度。最差情况下需完整遍历 t 。
• 空间复杂度 O(1) ： i , j 变量使用常数大小空间。

进阶问题解法

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

这种类似对同一个长字符串做很多次匹配的 ，可以像 KMP 算法一样，先用一些时间将长字符串中的数据 提取出来，磨刀不误砍柴功。有了提取好的数据，就可以快速的进行匹配。

• 先看上面双指针的问题慢在哪里？ 判断 s = "abc" 是不是 t = "ahbgdc" 的子序列。双指针是这样走的：

t:  a  h  b  g  d  c
    0  1  2  3  4  5

• 找 'a'：从 t[0] 开始，t[0]='a' 命中！下次从 t[1] 开始
• 找 'b'：从 t[1] 开始，t[1]='h' 不是，往后挪 → t[2]='b' 命中！下次从 t[3] 开始
• 找 'c'：从 t[3] 开始，t[3]='g' 不是 → t[4]='d' 不是 → t[5]='c' 命中！

• 注意"找 'b'"和"找 'c'"那两步：指针在 t 里一格一格地往后挪，挪过的 'h'、'g'、'd' 都是白挪的。

• 如果有 10 亿个 s，每个 s 都要这样在 t 里一格格挪，重复劳动太多了。

核心问题就一句话： 我站在 t 的某个位置，想知道"往右边最近的 'b' 在哪"，双指针只能一步步找。能不能提前算好、一步跳过去？

所以我希望有这么一张表，能直接回答这个问题:

• "站在 t 的位置 i，往右边（包括 i 自己）最近的要查找的字符 x 在第几格？"

• 如果有了这张表，"找 'b'"就不用一格格挪了，直接查表，一步到位。

我把这张表叫 dp，它有两个维度:

• 第一维 i：我现在站在 t 的哪个位置（0 ~ m）。
• 第二维 c：我要找哪个字符（'a''z'，用 0 ~ 25 表示）。

dp[i][c] = 站在位置 i，往右找字符 c，第一次遇到它的下标

找不到怎么办？ 用一个特殊值 m（t 的长度，一个不可能是真实下标的值）表示"右边没有这个字符了"。

第三步：手工填出 t = "ahbgdc" 的表（只看 b、d、c 三列）

先别管代码，我们用脑子想，从最右边往左填。为什么从右往左，待会就明白了。

t:   a    h    b    g    d    c
i:   0    1    2    3    4    5      6(哨兵,啥都没有)

先填哨兵行 i=6（站在 t 的末尾之外，右边什么都没有）：

dp[6][任何字符] = 6   （都找不到）

• 填 i=5（t[5]='c'）：站在位置 5，往右（含自己）找各字符。

  • 找 'c'：我脚下就是 'c'！→ dp[5]['c'] = 5
  • 找 'b'：脚下不是 b，那就看"位置 6 往右找 b"的答案 = dp[6]['b'] = 6 → dp[5]['b'] = 6
  • 找 'd'：脚下不是 d，看 dp[6]['d'] = 6 → dp[5]['d'] = 6

• 填 i=4（t[4]='d'）：

  • 找 'd'：脚下就是 'd'！→ dp[4]['d'] = 4
  • 找 'c'：脚下不是 c，看右边 dp[5]['c'] = 5 → dp[4]['c'] = 5
  • 找 'b'：脚下不是 b，看右边 dp[5]['b'] = 6 → dp[4]['b'] = 6

• 填 i=3（t[3]='g'）：

  • 找 'b'：脚下是 g，不是 b，看右边 dp[4]['b'] = 6 → dp[3]['b'] = 6
  • 找 'c'：脚下不是 c，看右边 dp[4]['c'] = 5 → dp[3]['c'] = 5
  • 找 'd'：脚下不是 d，看右边 dp[4]['d'] = 4 → dp[3]['d'] = 4

• 填 i=2（t[2]='b'）：

  • 找 'b'：脚下就是 'b'！→ dp[2]['b'] = 2
  • 找 'c'：脚下不是，看右边 dp[3]['c'] = 5 → dp[2]['c'] = 5

• 填 i=1（t[1]='h'）、i=0（t[0]='a'） 同理沿用右边。

填完后这三列长这样：

i:           0    1    2    3    4    5    6
dp[i]['b']:  2    2    2    6    6    6    6
dp[i]['c']:  5    5    5    5    5    5    6
dp[i]['d']:  4    4    4    4    4    6    6

你看上面每一格，无非两种情况：

• 规则 1：我脚下的字符 t[i] 正好就是要找的 c → 那不用往右看了，答案就是我自己：dp[i][c] = i

• 规则 2：我脚下的字符不是 c → 那"从我这往右找 c"和"从我右边一格往右找 c"是一样的，直接抄右边邻居的答案：dp[i][c] = dp[i+1][c]

if (t[i] - 'a' == c) {
    dp[i][c] = i            // 规则1：脚下就是
} else {
    dp[i][c] = dp[i + 1][c] // 规则2：抄右邻居
}

为什么必须从右往左填？ 因为规则 2 要用到 dp[i+1]（右边邻居）的结果。我得先把右边算好，左边才能抄。所以从最右的哨兵行开始，一路往左推。

这就像接力：最右边的人先确定答案，然后每个人看一眼右手边的人，要么"我自己就是"，要么"跟右手边一样"。

用这张表判断 s = "abc"（看跳跃的过程）

准备一个变量 pos，表示"我现在站在 t 的哪个位置开始找"，初始 pos = 0。

• 要找 'a'：查 dp[0]['a']

  • （这列没列出来，但 t[0]='a'，所以 dp[0]['a']=0）
  • 结果 0，不是哨兵 6 → 命中位置 0
  • 下次从 0 的下一格开始：pos = 0 + 1 = 1

• 要找 'b'：查 dp[1]['b'] = 2

  • 结果 2，不是 6 → 命中位置 2（注意！直接从 1 跳到 2，没有经过 h）
  • 下次从：pos = 2 + 1 = 3

• 要找 'c'：查 dp[3]['c'] = 5

  • 结果 5，不是 6 → 命中位置 5（直接从 3 跳到 5，跳过了 g、d）
  • 下次从：pos = 5 + 1 = 6

• s 的字符全部找完了 → "abc" 是子序列 ✅

看到了吗？找 'b' 和找 'c' 时，指针是"跳"过去的，不是一格格挪的。 跳过的 h、g、d 一次都没碰，这就是提速的关键。

再看一个失败的例子 s = "bd"（b 在前 d 在后，但 t 里 d 在 b... 不对，t 里 b 在位置 2，d 在位置 4，b 在 d 前面，所以 "bd" 应该是子序列）。换 s = "db":

• pos = 0
• 找 'd'：dp[0]['d'] = 4 → 命中 4 → pos = 5
• 找 'b'：dp[5]['b'] = 6 == 哨兵！→ 位置 5 往右没有 b 了 → 返回 false ✅
• "db" 不是子序列（t 里 d 在 b 后面，没法先 d 后 b），结果正确。

查询时的两条规则

判断 s 时，对每个字符 ch，查 dp[pos][ch]：

val c = ch - 'a'
if (dp[pos][c] == tLen) {   // 等于哨兵值，说明右边没这个字符了
    return false
}
pos = dp[pos][c] + 1        // 跳到命中位置的下一格，准备找下一个字符

• 查出来是哨兵 m → 右边找不到了 → s 不是子序列。

• 否则 → 跳到 命中位置 + 1，继续找 s 的下一个字符。

• s 全部字符顺利找完 → 返回 true。

一句话总结整个方法

• 预处理： 给 t 建一张表，记下"从每个位置往右，每个字母最近在哪"，从右往左填（脚下是就填自己，不是就抄右邻居）。

• 查询： 来一个 s，就拿着 pos 在表里一路"跳",跳到哨兵就失败，全跳完就成功。

因为查询时完全不碰 t 本身、只查表跳跃，所以每个 s 只花 O(|s|) 时间，跟 t 多长没关系——这正是 10 亿个 s 场景下能扛住的原因。

class Solution {
    fun isSubsequence(s: String, t: String): Boolean {
        val m = t.length

        // ===== 预处理：构建 dp 表 =====
        // dp[i][c] = 从 t 的位置 i（含 i）往右，字符 c 首次出现的下标；找不到记为 m
        // 多开一行 dp[m] 作哨兵行，全部初始化为 m
        val dp = Array(m + 1) { IntArray(26) { m } }

        // 从右往左递推（情况 B 需要用到右邻居 dp[i+1]）
        for (i in m - 1 downTo 0) {
            for (c in 0 until 26) {
                dp[i][c] = if (t[i] - 'a' == c) {
                    // 情况 A：脚下就是字符 c
                    i
                } else {
                    // 情况 B：抄右邻居的结果
                    dp[i + 1][c]
                }
            }
        }

        // ===== 查询：拿着 pos 在表里跳 =====
        var pos = 0  // 接下来从 t 的哪个位置开始找
        for (ch in s) {
            val c = ch - 'a'
            if (dp[pos][c] == m) {
                // 触发哨兵：右边再无此字符
                return false
            }
            // 跳到命中位置的下一格
            pos = dp[pos][c] + 1
        }
        // s 全部字符匹配成功
        return true
    }
}

//进阶问题的解决 
public boolean isSubsequence(String s, String t) {

    //考虑到  对第一个字符的处理 ，在t 之前一个空字符
    t=' '+t;

    //对t长字符串 做预处理
    //存储每一个位置上  a--z的下一个字符出现的位置
    int[][] dp = new int[t.length()][26];
    //依次对每个字符作处理
    for (char c = 'a'; c <= 'z'; c++) {
        //表示接下来不会在出现该字符
        int nextPos = -1;

        //从最后一位开始处理
        for (int i = t.length() - 1; i >= 0; i--) {
            //dp[i][c-'a']  加上外层循环  就是对每一个位置的a---z字符的处理了
            dp[i][c - 'a'] = nextPos;
            if (t.charAt(i) == c) {//表示当前位置有该字符  那么指向下一个该字符出现的位置就要被更新  为i
                nextPos = i;
            }
        }
    }

    //数据的利用 ，开始匹配
    int index=0;
    for (char c:s.toCharArray()){
        index=dp[index][c-'a'];//因为加了' '，所以之后在处理第一个字符的时候  如果是在第一行，就会去第一行，不影响之后字符的判断
        if(index==-1){
            return false;
        }
    }
    return true;
}

哨兵值 m 到底干嘛的

m（也就是 t.length）是一个永远不可能是真实下标的值（真实下标是 0 ~ m-1）。我们借它表示一个特殊状态："右边再也找不到这个字符了"。

它有两个作用：

• 作用 A：作为"找不到"的标记，让查询能判断失败，查询时：

  • if (dp[pos][c] == tLen) return false // tLen 就是 m，查到哨兵 = 找不到 = 失败

  • 如果 dp[pos][c] 是个真实下标（0 ~ m-1），说明右边有这个字符，能继续；如果等于 m，说明右边没了，直接判定 s 不是子序列。

• 作用 B：作为哨兵行，让填表的"抄右邻居"不越界

  • 填表时情况 B 要抄 dp[i+1]。当 i = m-1（最后一个真实字符）时，dp[i+1] = dp[m]，已经超出真实范围了。

  • 我们多开一行 dp[m]，整行填成 m，专门接住这个边界。这样 i = m-1 抄 dp[m] 时，抄到的就是 m（表示"末尾右边啥都没有"），逻辑自然成立，不用写特殊的 if 判断。

  • dp[m][所有字符] = m ← 哨兵行，初始化时全填 m

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!