力扣经典150题解析之二十六：判断子序列
1. 介绍
在这篇文章中，我们将解析力扣经典150题中的第二十六题：判断子序列。给定字符串 s 和 t，我们需要判断 s 是否为 t 的子序列。
2. 问题描述
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
3. 示例
示例 1:
输入：s = "abc", t = "ahbgdc" 输出：true 解释："abc" 是 "ahbgdc" 的子序列。
示例 2:
输入：s = "axc", t = "ahbgdc" 输出：false 解释："axc" 不是 "ahbgdc" 的子序列。
4. 解题思路
我们可以使用双指针的方法来解决这个问题：
- 使用两个指针 i 和 j 分别指向字符串 s 和 t 的开头。
- 不断尝试将指针i所指向的字符与指针j所指向的字符进行比较：
- 如果相同，将指针 i 向后移动一位，指针 j 向后移动一位。
- 如果不同，只将指针 j 向后移动一位。
- 如果指针 i 移动到了 s 的末尾，则说明 s 是 t 的子序列，返回 true；否则 t 遍历完成后仍未找到匹配的子序列，返回 false。
5. 代码实现
public class Solution { public boolean isSubsequence(String s, String t) { int sPointer = 0, tPointer = 0; int sLen = s.length(), tLen = t.length(); while (sPointer < sLen && tPointer < tLen) { if (s.charAt(sPointer) == t.charAt(tPointer)) { sPointer++; } tPointer++; } return sPointer == sLen; } }
6. 复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 t 的长度。双指针遍历一次字符串 t。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
7. 测试与验证
我们对示例输入进行测试：
public class Main { public static void main(String[] args) { Solution solution = new Solution(); String s1 = "abc", t1 = "ahbgdc"; System.out.println("是否为子序列：" + solution.isSubsequence(s1, t1)); // 输出 true String s2 = "axc", t2 = "ahbgdc"; System.out.println("是否为子序列：" + solution.isSubsequence(s2, t2)); // 输出 false } }
8. 总结
通过使用双指针遍历字符串 s 和 t，我们可以有效地判断字符串 s 是否为字符串 t 的子序列。在遍历过程中，我们不断尝试将指针 sPointer 所指向的字符与指针 tPointer 所指向的字符进行比较，直到 s 的所有字符都被匹配或者 t 遍历完成。
9. 扩展
对于大量输入的情况，我们可以通过优化算法或者使用数据结构来提高效率，例如使用哈希表或者预处理字符串 t 的索引信息等方式。
