LeetCode392-判断子序列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/is-subsequence/

中文链接：https://leetcode-cn.com/problems/is-subsequence/

题目详述

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

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

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

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

后续挑战 :

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

题目详解

每次记录待查询的起点，对每个 s 中的字符直接在 t 中进行查询，若找不到对应字符，说明 s 不可能为 t 的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00392 {

    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            // 每次从下一个位置开始找
            index = t.indexOf(c, index + 1);
            // 没找到
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

后续挑战 ：如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。设 S 的长度为 M，T 的长度为 N，则上面的做法时间复杂度为 O(kMN)。由于 T 对于每个 S 而言是相同的，可以对 T 进行处理，进行优化。

  • 按升序记录每个字符在 T 中出现的下标（对于多个 S 而言，只需要执行一次）。
  • 对于每一个 S，进行遍历并在对应字符的下标集合中进行二分查找，看是否能找到满足条件的下标（由 index 进行维护）。
  • 只要上述过程有不满足条件的地方，说明 S 不可能为 T 的子序列，可以直接返回 false。

可以认为二分查找的过程平均时间复杂度为 O(logX)，最坏情况下为 O(N)，并且 O(logX) 远小于 O(N)。对于每一个 S ，时间复杂度为 O(MlogX)。对于 k 个 S，时间复杂度为 O(kMlogX)。

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
28
29
30
31
32
33
34
35
public class LeetCode_00392 {

    // 进阶挑战（有大量输入的 S，T 相同）
    public boolean isSubsequence(String s, String t) {
        // 数组的每个元素是一个列表，用来存储对应字符的下标集合
        List<Integer>[] map = new ArrayList[26];
        for (int i = 0; i < t.length(); ++i) {
            int tmp = t.charAt(i) - 'a';
            if (map[tmp] == null) {
                map[tmp] = new ArrayList<>();
            }
            map[tmp].add(i);
        }
        int index = 0;
        for (char c : s.toCharArray()) {
            List<Integer> list = map[c - 'a'];
            // 对应列表不存在
            if (list == null) {
                return false;
            }
            // 在对应列表中进行二分查找，得到在列表中的插入点
            int indexOfList = Collections.binarySearch(list, index);
            if (indexOfList < 0) {
                indexOfList = -indexOfList - 1;
            }
            // 没找到
            if (indexOfList == list.size()) {
                return false;
            }
            // 更新 index
            index = list.get(indexOfList) + 1;
        }
        return true;
    }
}