392. 判断子序列

题目描述

输入字符串 s 和 t。判断 s 是不是 t 的子序列。

子序列的意思是：从 t 中删去若干字符（也可以一个都不删），剩余字符不改变先后次序，得到的字符串。例如 "ace" 是 "abcde" 的子序列，"aec" 则不是。

是子序列返回 true，否则返回 false。空串是任何字符串的子序列。

示例 1

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

解释：在 t 中能依次找到 a、b、c。

示例 2

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

解释：t 中没有字符 x。

数据范围

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只含小写英文字母

进阶：如果有海量的 s（S1, S2, ..., Sk，k 达到 10 亿级）要逐个判断是否为同一个 t 的子序列，应如何改进？

解题思路

指针 i 指向 s 中下一个待匹配的字符。从左到右扫描 t，遇到与 s[i] 相同的字符就把 i 前移。贪心地尽早匹配不会吃亏：更早匹配只会给后面留下更多字符。扫完后 i 等于 len(s) 就是子序列。

为什么正确

s[0..i) 已经是 t 当前已扫描前缀的子序列，且 i 是所有匹配方式中最大的。

复杂度分析

时间 O(|t|)，空间 O(1)。

易错点

空串 s 是任何字符串的子序列；匹配完 s 后要防止 s[i] 越界（先判断 i < len(s)）。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        for c in t:
            if i < len(s) and s[i] == c:
                i += 1
        return i == len(s)

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        for (char c : t.toCharArray())
            if (i < s.length() && s.charAt(i) == c)
                i++;
        return i == s.length();
    }
}

class Solution {
public:
    bool isSubsequence(string s, string t) {
        size_t i = 0;
        for (char c : t)
            if (i < s.size() && s[i] == c)
                i++;
        return i == s.size();
    }
};

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

var isSubsequence = function(s, t) {
    let i = 0;
    for (const c of t)
        if (i < s.length && s[i] === c)
            i++;
    return i === s.length;
};

function isSubsequence(s: string, t: string): boolean {
    let i = 0;
    for (const c of t)
        if (i < s.length && s[i] === c)
            i++;
    return i === s.length;
}

载入编辑器，自己跑一遍 →

其他解法

双指针最简单，适合单次查询；预处理 + 动态规划和二分查找都先处理 t，前者查询更快，后者占用空间更少。

解法 2：预处理 + 动态规划时间 O(26m + n)，空间 O(26m)

设 m 为 t 的长度，n 为 s 的长度。从后往前填表 f[i][c]，表示从位置 i 开始字符 c 第一次出现的位置，不存在记为 m。匹配 s 时，当前位置 j 每次直接跳到 f[j][c] + 1。跳到 m 说明匹配失败。

预处理比双指针多占 O(26m) 空间。预处理只做一次，之后每个 s 只需 O(n) 时间，适合进阶问题里大量 s 查询同一个 t 的场景。

class Solution:
    def isSubsequence(self, s, t):
        m = len(t)
        f = [[m] * 26 for _ in range(m + 1)]
        for i in range(m - 1, -1, -1):
            f[i] = f[i + 1][:]
            f[i][ord(t[i]) - 97] = i
        j = 0
        for c in s:
            nxt = f[j][ord(c) - 97]
            if nxt == m:
                return False
            j = nxt + 1
        return True

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = t.length();
        int[][] f = new int[m + 1][26];
        Arrays.fill(f[m], m);
        for (int i = m - 1; i >= 0; i--) {
            f[i] = f[i + 1].clone();
            f[i][t.charAt(i) - 'a'] = i;
        }
        int j = 0;
        for (char c : s.toCharArray()) {
            int nxt = f[j][c - 'a'];
            if (nxt == m) return false;
            j = nxt + 1;
        }
        return true;
    }
}

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = t.size();
        vector<vector<int>> f(m + 1, vector<int>(26, m));
        for (int i = m - 1; i >= 0; i--) {
            f[i] = f[i + 1];
            f[i][t[i] - 'a'] = i;
        }
        int j = 0;
        for (char c : s) {
            int nxt = f[j][c - 'a'];
            if (nxt == m) return false;
            j = nxt + 1;
        }
        return true;
    }
};

func isSubsequence(s string, t string) bool {
	m := len(t)
	f := make([][26]int, m+1)
	for c := 0; c < 26; c++ {
		f[m][c] = m
	}
	for i := m - 1; i >= 0; i-- {
		f[i] = f[i+1]
		f[i][t[i]-'a'] = i
	}
	j := 0
	for i := 0; i < len(s); i++ {
		nxt := f[j][s[i]-'a']
		if nxt == m {
			return false
		}
		j = nxt + 1
	}
	return true
}

var isSubsequence = function(s, t) {
    const m = t.length;
    const f = new Array(m + 1);
    f[m] = new Array(26).fill(m);
    for (let i = m - 1; i >= 0; i--) {
        f[i] = f[i + 1].slice();
        f[i][t.charCodeAt(i) - 97] = i;
    }
    let j = 0;
    for (let i = 0; i < s.length; i++) {
        const nxt = f[j][s.charCodeAt(i) - 97];
        if (nxt === m) return false;
        j = nxt + 1;
    }
    return true;
};

function isSubsequence(s: string, t: string): boolean {
    const m = t.length;
    const f: number[][] = new Array(m + 1);
    f[m] = new Array<number>(26).fill(m);
    for (let i = m - 1; i >= 0; i--) {
        f[i] = f[i + 1].slice();
        f[i][t.charCodeAt(i) - 97] = i;
    }
    let j = 0;
    for (let i = 0; i < s.length; i++) {
        const nxt = f[j][s.charCodeAt(i) - 97];
        if (nxt === m) return false;
        j = nxt + 1;
    }
    return true;
}

解法 3：下标列表 + 二分查找时间 O(m + n log m)，空间 O(m)

预处理时记录每个字符在 t 中出现的下标列表。匹配 s 的每个字符时，在它的下标列表里二分查找第一个大于上一次匹配位置的下标。找不到就返回 false。

空间只有 O(m)，比动态规划表小。每次匹配多一个 log m 因子。同样适合大量查询的进阶场景。

from bisect import bisect_right


class Solution:
    def isSubsequence(self, s, t):
        pos = [[] for _ in range(26)]
        for i, c in enumerate(t):
            pos[ord(c) - 97].append(i)
        prev = -1
        for c in s:
            lst = pos[ord(c) - 97]
            k = bisect_right(lst, prev)
            if k == len(lst):
                return False
            prev = lst[k]
        return True

class Solution {
    public boolean isSubsequence(String s, String t) {
        List<List<Integer>> pos = new ArrayList<>();
        for (int c = 0; c < 26; c++) pos.add(new ArrayList<>());
        for (int i = 0; i < t.length(); i++) pos.get(t.charAt(i) - 'a').add(i);
        int prev = -1;
        for (char c : s.toCharArray()) {
            List<Integer> lst = pos.get(c - 'a');
            int lo = 0, hi = lst.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (lst.get(mid) > prev) hi = mid;
                else lo = mid + 1;
            }
            if (lo == lst.size()) return false;
            prev = lst.get(lo);
        }
        return true;
    }
}

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> pos(26);
        for (int i = 0; i < (int)t.size(); i++) pos[t[i] - 'a'].push_back(i);
        int prev = -1;
        for (char c : s) {
            auto& lst = pos[c - 'a'];
            auto it = upper_bound(lst.begin(), lst.end(), prev);
            if (it == lst.end()) return false;
            prev = *it;
        }
        return true;
    }
};

func isSubsequence(s string, t string) bool {
	pos := make([][]int, 26)
	for i := 0; i < len(t); i++ {
		pos[t[i]-'a'] = append(pos[t[i]-'a'], i)
	}
	prev := -1
	for i := 0; i < len(s); i++ {
		lst := pos[s[i]-'a']
		lo, hi := 0, len(lst)
		for lo < hi {
			mid := (lo + hi) / 2
			if lst[mid] > prev {
				hi = mid
			} else {
				lo = mid + 1
			}
		}
		if lo == len(lst) {
			return false
		}
		prev = lst[lo]
	}
	return true
}

var isSubsequence = function(s, t) {
    const pos = Array.from({ length: 26 }, () => []);
    for (let i = 0; i < t.length; i++) pos[t.charCodeAt(i) - 97].push(i);
    let prev = -1;
    for (let i = 0; i < s.length; i++) {
        const lst = pos[s.charCodeAt(i) - 97];
        let lo = 0, hi = lst.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (lst[mid] > prev) hi = mid;
            else lo = mid + 1;
        }
        if (lo === lst.length) return false;
        prev = lst[lo];
    }
    return true;
};

function isSubsequence(s: string, t: string): boolean {
    const pos: number[][] = Array.from({ length: 26 }, () => []);
    for (let i = 0; i < t.length; i++) pos[t.charCodeAt(i) - 97].push(i);
    let prev = -1;
    for (let i = 0; i < s.length; i++) {
        const lst = pos[s.charCodeAt(i) - 97];
        let lo = 0, hi = lst.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (lst[mid] > prev) hi = mid;
            else lo = mid + 1;
        }
        if (lo === lst.length) return false;
        prev = lst[lo];
    }
    return true;
}

双指针专题的其他题目

查看双指针全部题目 →