leetcode 392 判断子序列

zhaojun

2022 年 08 月 30 日

1914 次浏览

暂无评论

538字数

默认分类

# [392. 判断子序列](https://leetcode.cn/problems/is-subsequence)

## 题目

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

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

**进阶：**

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

**致谢：**

特别感谢 [@pbrother ](https://leetcode.com/pbrother/)添加此问题并且创建所有测试用例。

**示例 1：**

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

**示例 2：**

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

**提示：**

- `0 <= s.length <= 100`
- `0 <= t.length <= 10^4`
- 两个字符串都只由小写字符组成。

## 题解 1

声明 lastIndex 为最后一个存在的元素，遍历 s 的每个元素计为 a

- 从 lastIndex 开始从 t 中找，包含 a 时，则继续循环。
- 不包含，则表示不是子序列，直接返回。

时间复杂度 O(n)，空间复杂度 O(1)

```java
class Solution {
    public boolean isSubsequence(String s, String t) {
        int lastIndex = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            int index = t.indexOf(a, lastIndex);
            if (index == -1) {
                return false;
            } else {
                lastIndex = index + 1;
            }
        }

return true;
    }
}
```

## 题解 2

这是动态规划的解法，等学到动态规划再看。 https://leetcode.cn/problems/is-subsequence/solution/pan-duan-zi-xu-lie-by-leetcode-solution/

```java
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;
    }
}
```

## 题解 3

二分法  https://labuladong.github.io/algo/4/33/133/

```java
boolean isSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    // 对 t 进行预处理
    ArrayList<Integer>[] index = new ArrayList[256];
    for (int i = 0; i < n; i++) {
        char c = t.charAt(i);
        if (index[c] == null) 
            index[c] = new ArrayList<>();
        index[c].add(i);
    }
    
    // 串 t 上的指针
    int j = 0;
    // 借助 index 查找 s[i]
    for (int i = 0; i < m; i++) {
        char c = s.charAt(i);
        // 整个 t 压根儿没有字符 c
        if (index[c] == null) return false;
        int pos = left_bound(index[c], j);
        // 二分搜索区间中没有找到字符 c
        if (pos == -1) return false;
        // 向前移动指针 j
        j = index[c].get(pos) + 1;
    }
    return true;
}
```

最后修改：2022 年 08 月 30 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 392 判断子序列

zhaojun • 2022 年 08 月 30 日

leetcode 392 判断子序列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

leetcode 257 二叉树的所有路径

leetcode 724 寻找数组的中心下标

leetcode 2016 增量元素之间的最大差值

Shiro 学习 11 - 集成 Spring 之记住我

浅谈如何在大陆服务器加速访问 github 和 k8s.gcr.io 等资源 - sniproxy

leetcode 392 判断子序列

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 392 判断子序列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款