【双指针】392. 判断子序列【简单】

2024-05-11 16:52
文章标签 简单 指针 判断 序列 392

本文主要是介绍【双指针】392. 判断子序列【简单】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

判断子序列

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

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

进阶:

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

解题思路

为了判断字符串 s 是否为字符串 t 的子序列,可以使用双指针技巧。

  • 1、将两个指针分别指向字符串 s 和 t 的开头,然后逐个字符地比较,如果字符相等,则将两个指针都向后移动;
  • 2、如果不相等,则只将指针指向字符串 t 的指针向后移动。
  • 3、最后,如果字符串 s 的指针遍历完毕,则说明 s 是 t 的子序列,返回 true;否则,返回 false。

Java实现

public class IsSubsequence {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();}public static void main(String[] args) {IsSubsequence isSubsequence = new IsSubsequence();String s1 = "abc", t1 = "ahbgdc";System.out.println("Is Subsequence: " + isSubsequence.isSubsequence(s1, t1)); // Expected: trueString s2 = "axc", t2 = "ahbgdc";System.out.println("Is Subsequence: " + isSubsequence.isSubsequence(s2, t2)); // Expected: false}
}

时间空间复杂度

  • 时间复杂度: 在最坏情况下,时间复杂度为 O(max(m, n)),其中 n 是字符串 s 的长度,m 是字符串 t 的长度。
  • 空间复杂度: 使用了常数级的额外空间,空间复杂度为 O(1)。

进阶解题思路

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

在这种情况下,我们需要考虑优化算法以提高效率,因为有大量输入的 S 需要逐个检查是否为 T 的子序列。

  • 可以考虑使用预处理的方法来加速匹配过程。

  • 1、一种可行的方法是对字符串 T 进行预处理,构建一个哈希表或者数组,其中键或者索引表示字符, 值表示在字符串 T 中出现该字符的所有位置。

  • 2、对于每个输入的字符串 S,可以遍历其字符,并在预处理的哈希表或数组中查找下一个字符的位置。

  • 3、如果找到了,则更新当前位置,继续查找下一个字符。

  • 4、如果遍历完字符串 S 后,能够成功找到每个字符的位置,则说明 S 是 T 的子序列。

这种预处理的方法可以大大减少每次检查的时间复杂度,因为在预处理过程中可以一次性获取到每个字符在字符串 T中的所有位置,而在检查过程中只需要根据当前字符在哈希表或数组中查找下一个位置即可,无需重新遍历字符串 T。

进阶Java实现

public class IsSubsequenceAdvanced {//预处理mapMap<Character, List<Integer>> map = new HashMap<>();//初始化map,只需要处理一次public void initTarget(String t){//预处理字符串 T,构建字符位置哈希表for (int i = 0; i < t.length(); i++) {char ch = t.charAt(i);if (!map.containsKey(ch)) {map.put(ch, new ArrayList<>());}map.get(ch).add(i);}}//进行字符串匹配public boolean isSubsequenceAdvanced (String s) {int prevIndex = -1; // 上一个字符的位置// 遍历字符串 S,并根据预处理的哈希表查找下一个字符的位置for (char ch : s.toCharArray()) {if (!map.containsKey(ch)) {return false; // 字符不存在于字符串 T 中,直接返回 false}List<Integer> positions = map.get(ch);// 在当前字符的位置列表中查找大于上一个字符位置的最小位置int nextIndex = binarySearch(positions, prevIndex);if (nextIndex == -1) {return false; // 找不到大于上一个字符位置的位置,直接返回 false}prevIndex = nextIndex;}return true;}// 二分查找大于给定位置的最小位置private int binarySearch(List<Integer> positions, int target) {int left = 0, right = positions.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (positions.get(mid) <= target) {left = mid + 1;} else {right = mid - 1;}}return left < positions.size() ? positions.get(left) : -1;}public static void main(String[] args) {IsSubsequenceAdvanced isSubsequence = new IsSubsequenceAdvanced();String s1 = "abc",s2="hgc", t1 = "ahbgdc";isSubsequence.initTarget(t1);// Expected: trueSystem.out.println(isSubsequence.isSubsequenceAdvanced(s1));// Expected: trueSystem.out.println(isSubsequence.isSubsequenceAdvanced(s2));}
}

进阶时间空间复杂度

  • 时间复杂度: 第一次时间复杂度为 O(n+m),后续的时间复杂度在介于O(1)到O(n)之间,其中 n 是字符串 s 的长度,m 是字符串 t 的长度。
    但是只要是目标串t比较长(m比较大),s比较短(n比较多),那算法的效率就比较高
  • 空间复杂度: 空间复杂度为 O(m)。

这篇关于【双指针】392. 判断子序列【简单】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/980113

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

uva 10130 简单背包

题意: 背包和 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p