LeetCode题练习与总结：判断子序列--392

一、题目描述

给定字符串 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
两个字符串都只由小写字符组成。

二、解题思路

这个问题可以通过双指针的方法来解决。我们定义两个指针，一个指向字符串s，另一个指向字符串t。我们遍历字符串t，每当我们遇到一个与s中当前字符相同的字符时，我们就移动s的指针。如果s的指针能够移动到s的末尾，那么s就是t的子序列。

(一) 基本实现

初始化两个指针i和j，分别指向s和t的起始位置。
遍历字符串t，如果t[j] == s[i]，则i++。
如果i等于s的长度，返回true。
如果遍历完t后，i不等于s的长度，返回false。

(二) 进阶问题

对于进阶问题，如果需要检查大量的s字符串是否为t的子序列，我们可以预处理t来创建一个映射，记录t中每个字符出现的位置。这样，对于每个s，我们可以快速地检查它是否为t的子序列，而不需要每次都遍历t。

三、具体代码

以下是基本实现的Java代码：

class Solution {public boolean isSubsequence(String s, String t) {int i = 0, j = 0;while (i < s.length() && j < t.length()) {if (s.charAt(i) == t.charAt(j)) {i++;}j++;}return i == s.length();}
}

以下是进阶问题的预处理和检查方法的Java代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;class Solution {Map<Character, List<Integer>> indexMap;public boolean isSubsequence(String s, String t) {// 预处理tpreprocess(t);// 检查s是否为t的子序列return checkSubsequence(s);}private void preprocess(String t) {indexMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);indexMap.computeIfAbsent(c, x -> new ArrayList<>()).add(i);}}private boolean checkSubsequence(String s) {int prevIndex = -1;for (char c : s.toCharArray()) {if (!indexMap.containsKey(c)) {return false;}List<Integer> indices = indexMap.get(c);int pos = binarySearch(indices, prevIndex);if (pos == -1) {return false;}prevIndex = indices.get(pos) + 1;}return true;}private int binarySearch(List<Integer> indices, int target) {int left = 0, right = indices.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (indices.get(mid) > target) {right = mid - 1;} else {left = mid + 1;}}return left < indices.size() && indices.get(left) > target ? left : -1;}
}

这里的preprocess方法预处理了字符串t，checkSubsequence方法用于检查字符串s是否为t的子序列。binarySearch方法用于在预处理后的列表中找到第一个大于target的索引。

四、时间复杂度和空间复杂度

(一) 基本实现

1. 时间复杂度

代码的时间复杂度主要取决于字符串s和t的长度。

while循环的条件是i < s.length()和j < t.length()，这意味着循环会持续直到至少一个字符串被完全遍历。
在循环内部，我们执行了常数时间的操作（比较字符和增加指针）。

因此，循环将执行O(s.length() + t.length())次。这是因为每次循环中，我们至少将j增加1，直到t被完全遍历，而i的增加则最多与s的长度相同。所以，时间复杂度是O(n + m)，其中n是字符串t的长度，m是字符串s的长度。

2. 空间复杂度

代码的空间复杂度主要取决于除了输入字符串之外所使用的额外空间。

i和j是两个整型变量，它们占用的空间是常数，即O(1)。
没有使用任何其他的数据结构，如数组、列表或哈希表。

因此，空间复杂度是O(1)，因为无论输入字符串s和t的长度如何，使用的额外空间都不会改变。

(二) 进阶问题

1. 时间复杂度

代码的时间复杂度可以分为预处理阶段和检查子序列阶段。

(1) 预处理阶段

preprocess 方法：
- 遍历字符串 t，其长度为 n。
- 对于每个字符 c，将其索引添加到对应的列表中，这是一个常数时间的操作。
因此，预处理的时间复杂度为 O(n)。

(2) 检查子序列阶段

checkSubsequence 方法：
- 遍历字符串 s，其长度为 m。
- 对于 s 中的每个字符，我们执行以下操作：
  - 检查字符是否在 indexMap 中，这是常数时间的操作。
  - 使用 binarySearch 方法在对应的索引列表中查找第一个大于 prevIndex 的位置。
  - binarySearch 方法的时间复杂度为 O(log k)，其中 k 是列表中元素的数量，对于每个字符 c，k 最多为 n。
因此，检查子序列的总时间复杂度为 O(m log n)。

综合两个阶段，总的时间复杂度为 O(n + m log n)。

2. 空间复杂度

indexMap：
- 存储了字符串 t 中每个字符的所有索引位置。
- 假设字符集大小为 C（对于小写字母，C 为 26），在最坏情况下，indexMap 可能包含 n 个条目，每个条目对应一个字符的索引列表。
- 每个列表的平均长度为 n / C，所以总的存储空间为 O(n)。
binarySearch 方法：
- 使用了常数额外空间，即 O(1)。

因此，总的空间复杂度为 O(n)。

五、总结知识点

(一) 基本实现

类定义：
- class Solution：定义了一个名为Solution的类。
方法定义：
- public boolean isSubsequence(String s, String t)：定义了一个公共方法isSubsequence，它接受两个字符串参数s和t，并返回一个布尔值。
变量声明与初始化：
- int i = 0, j = 0;：声明并初始化了两个整型变量i和j，用于在字符串s和t中遍历。
循环结构：
- while (i < s.length() && j < t.length())：使用while循环来遍历字符串s和t，直到至少一个字符串被完全遍历。
字符串操作：
- s.charAt(i)：使用charAt方法来获取字符串s中索引为i的字符。
- t.charAt(j)：使用charAt方法来获取字符串t中索引为j的字符。
条件判断：
- if (s.charAt(i) == t.charAt(j))：条件判断语句，用于检查字符串s和t在当前位置的字符是否相等。
变量自增：
- i++：当条件满足时，i的值自增，表示在字符串s中找到了一个匹配的字符。
- j++：无论条件是否满足，j的值都会自增，表示在字符串t中移动到下一个字符。
方法返回值：
- return i == s.length();：返回一个布尔值，表示字符串s是否完全在字符串t中找到，即s是否为t的子序列。
逻辑运算符：
- &&：逻辑与运算符，用于在while循环中组合两个条件。
比较运算符：
- ==：用于比较两个值是否相等。

(二) 进阶问题

类定义：
- class Solution：定义了一个名为 Solution 的类。
成员变量：
- Map<Character, List<Integer>> indexMap：定义了一个成员变量 indexMap，它是一个哈希表，键是字符，值是该字符在字符串中出现的索引列表。
构造方法：
- （无显式构造方法，但隐式有一个无参构造方法）。
方法定义：
- public boolean isSubsequence(String s, String t)：定义了一个公共方法 isSubsequence，它接受两个字符串参数并返回一个布尔值。
预处理方法：
- private void preprocess(String t)：定义了一个私有方法 preprocess，用于预处理字符串 t 并填充 indexMap。
检查子序列方法：
- private boolean checkSubsequence(String s)：定义了一个私有方法 checkSubsequence，用于检查字符串 s 是否为字符串 t 的子序列。
二分查找方法：
- private int binarySearch(List<Integer> indices, int target)：定义了一个私有方法 binarySearch，用于在有序列表 indices 中查找第一个大于 target 的索引。
数据结构：
- HashMap 和 ArrayList：使用了哈希表和动态数组来存储字符及其索引。
集合操作：
- computeIfAbsent：在 HashMap 中，如果键不存在，则计算其值并插入到映射中。
循环结构：
- for 循环：用于遍历字符串 t 并填充 indexMap。
- while 循环：在 binarySearch 方法中用于实现二分查找。
字符操作：
- char c = t.charAt(i)：获取字符串 t 中第 i 个位置的字符。
逻辑判断：
- if 和 else 语句：用于条件判断。
递增和递减操作：
- i++ 和 j++：用于在字符串中移动指针。
- left++ 和 right--：在二分查找中调整搜索范围。
返回值：
- return 语句：用于从方法中返回结果。
比较操作：
- > 和 >=：用于比较整数。