网站500兆空间多少钱,wordpress 图片集插件,肇庆高要建设局网站,教育网站建设的目的一、题目描述
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;ace是abcde的一…一、题目描述
给定字符串 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 1000 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 {MapCharacter, ListInteger 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;}ListInteger indices indexMap.get(c);int pos binarySearch(indices, prevIndex);if (pos -1) {return false;}prevIndex indices.get(pos) 1;}return true;}private int binarySearch(ListInteger 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方法预处理了字符串tcheckSubsequence方法用于检查字符串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 是列表中元素的数量对于每个字符 ck 最多为 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 的类。 成员变量 MapCharacter, ListInteger 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(ListInteger 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 语句用于从方法中返回结果。 比较操作 和 用于比较整数。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
