392.判断子序列

题目:392.判断子序列

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

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

• 示例 1：

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

• 示例 2：

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

• 提示：

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

• 进阶：

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

思路1

判断一个字符串 s 是否为另一个字符串 t 的子序列，可以使用双指针方法来实现。这个方法的时间复杂度为 O(n + m)，其中 n 是字符串 t 的长度，m 是字符串 s 的长度。

双指针方法

1. 初始化两个指针：

   • indexS 指向 s 的起始位置。
   • indexT 指向 t 的起始位置。

2. **遍历字符串 t**：

   • 当 indexS 小于 s 的长度并且indexT 小于 t 的长度时：
     • 如果 s[indexS] 等于 t[indexT]，则指针 indexS 向前移动一位。
     • 无论是否匹配，指针 indexT 都向前移动一位。
   • 当 indexS 达到 s 的长度时，说明 s 是 t 的子序列，返回 true。如果 indexS 没有达到 s 的长度，说明 s 不是 t 的子序列，返回 false。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public boolean isSubsequence(String s, String t) {
    int indexS = 0;
    int indexT = 0;
    while (indexS < s.length() && indexT < t.length()) {
        // 如果 s[indexS] 等于 t[indexT]，则指针 indexS 向前移动一位。
        if (s.charAt(indexS) == t.charAt(indexT)) {
            indexS++;
        }
        indexT++;
    }
    return indexS >= s.length();
}

思路2

对于大量的输入 S，称作 S1, S2, … , Sk，其中 k >= 10亿，可以通过预处理 T 使得每次判断更加高效。这个优化适合需要频繁检查大量子序列的场景。

1. 预处理：

   • 对字符串 t 进行预处理，创建一个字典 map，键是字符，值是字符在 t 中出现的所有位置的列表。

2. 查询：

   • 利用 Collections.binarySearch 在预处理的列表中查找字符的位置，并确保位置是递增的。
   • 对于 s 的每个字符 c，如果 t 中不包含 c, 直接返回false。在 map 中查找其出现的位置列表，然后使用 Collections.binarySearch 找到第一个大于 prevIndex 的位置。

3. Collections.binarySearch说明：

   • 在使用 Collections.binarySearch 时，如果待查找的值不存在于列表中，Collections.binarySearch 会返回一个负数。这个负数不仅表示未找到该值，还包含了额外的信息：该值应当插入的位置。如果搜索的值不存在，返回值 pos 会是 -(插入点) - 1。
   • 假设你在一个排序好的列表 list 中搜索一个值 val，返回值 pos 的含义如下：
     • pos >= 0：表示 val 存在于列表中，且 list[pos] == val。
     • pos < 0：表示 val 不存在于列表中，返回值 -(插入点) - 1。

• 时间复杂度:O(mlog₂n)
• 空间复杂度:O(n)

代码

public boolean isSubsequence(String s, String t) {
    HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
    // 预处理 t
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        map.putIfAbsent(c, new ArrayList<>());
        map.get(c).add(i);
    }
    int preIndex = -1;
    for (char c : s.toCharArray()) {
        // 如果 t 中不包含 s 的字符
        if (!map.containsKey(c)) {
            return false;
        }
        ArrayList<Integer> indexList = map.get(c);
        // 使用二分查找在 indexList 中找到比 prevIndex 大的最小值
        int pos = Collections.binarySearch(indexList, preIndex + 1);
        if (pos < 0) {
            pos = -pos - 1;
        }
        // 如果没有找到大于 prevIndex 的位置
        if (pos >= indexList.size()) {
            return false;
        }
        // 更新 prevIndex
        preIndex = indexList.get(pos);
    }
    return true;
}