当前位置：首页 > backend >正文

力扣经典算法篇-19-判断子序列(双指针法，双指针递归法，批量校验时的进阶解法（预处理+二分查找））

backend 2025/7/14 6:03:02

1、题干

给定字符串 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

2、解题

方法一：基础双指针法

使用两个指针，第一个指针指向字符串s的其实位置，第二个指针指向t的起始位置。
分别比较两个指针位置的元素值是否相等，如果相等两个指针同时右移，如果不相等仅t的指针右移即可。
最终查看s的指针有没有滑动到最后的位置，到了最后，说明s已经被全包含了。否则就是没有全包含，即s不是t的子序列。

代码示例：

 public static boolean isSubsequence(String s, String t) {int left1 = 0;int left2 = 0;while (left1 < s.length() && left2 < t.length()) {if (s.charAt(left1) == t.charAt(left2)) {left1++;}left2++;}if (left1 >= s.length()) {return true;}return false;}

方法二：双指针递归法

使用递归+首元素校验和移除的方式。（实际上和双指针的思路一致）
每次都取出两个字符串中的第0个元素进行比较。如果相等，s和t都移除首元素，取各自剩余的部分继续上诉递归处理；如果不相等，s不变，t移除首元素，取各自剩余的部分继续上诉递归处理；
递归终止掉件：s为空，说明s是t的子序列；如果t为空，说明s不是t的子序列。

代码示例：

public static boolean isSubsequence(String s, String t) {if (s.length() == 0) {return true;}if (t.length() == 0) {return false;}if (s.charAt(0) == t.charAt(0)) {s = s.substring(1);t = t.substring(1);return isSubsequence(s, t);}t = t.substring(1);return isSubsequence(s, t);
}

进阶解法：

方法三：（预处理 + 二分查找）

如果有多个s串，都要校验是否是t的子串，可以使用如上的双指针法循环处理。
也可以对t进行预处理，如:取出t中的每一个元素，并记录其存在的位置列表；
之后逐个比较s串，分别校验s的每一个字符是否存在t中的对应的列表；不存在直接判断不是子串，这样可以快速筛掉大量不满足的子串。
当然即使存在了，也要进一步校验是否满足，譬如上一个元素已经对应t的位置3了，下一个元素匹配的位置确是2，这肯定也不行。
只有同时满足存在列表，且当前子串得到的位置比之前的位置更靠后。才能满足是子序列的要求。

代码示例：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Test24 {private Map<Character, List<Integer>> charIndicesMap;public Test24(String t) {charIndicesMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);charIndicesMap.putIfAbsent(c, new ArrayList<>());charIndicesMap.get(c).add(i);}}public boolean isSubsequence(String s) {int prevIndex = -1; // 上一次匹配的位置for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);List<Integer> indices = charIndicesMap.get(c);if (indices == null) return false;// 使用二分查找找第一个大于prevIndex的值int pos = binarySearchGreaterThan(indices, prevIndex);if (pos == -1) return false;prevIndex = pos;}return true;}// 在有序列表中找第一个大于target的数private int binarySearchGreaterThan(List<Integer> list, int target) {int left = 0, right = list.size() - 1;int res = -1;while (left <= right) {int mid = left + (right - left) / 2;if (list.get(mid) > target) {res = list.get(mid);right = mid - 1;} else {left = mid + 1;}}return res;}public static void main(String[] args) {Test24 checker = new Test24("ahbgdc");System.out.println(checker.isSubsequence("abc")); // trueSystem.out.println(checker.isSubsequence("aec")); // falseSystem.out.println(checker.isSubsequence("bdc")); // trueSystem.out.println(checker.isSubsequence("abz")); // false}
}