有哪些做微博长图网站,电信cn2线路,企业官网首页源码,seo推广名词解释其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一#xff1a;双指针
三、代码
3.1 方法一#xff1a;双指针
3.1.1 Java易懂版#xff1a;… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一双指针
三、代码
3.1 方法一双指针
3.1.1 Java易懂版
3.1.2 Java优化版
3.1.3 C版本
3.1.4 Python版本
3.1.5 Go版本
四、复杂度分析
4.1 方法一双指针 前言
这是力扣的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 1000 t.length 10^4两个字符串都只由小写字符组成。 二、题解 2.1 方法一双指针
思路与算法
首先我们定义 i 和 j 两个指针用指针 i 来遍历字符串 s 用指针 j 来遍历字符串 t 。 当遍历完字符串 s 的时候退出循环即 i 小于字符串 s 的长度。 循环内部条件
当指针 j 指向的索引已经等于字符串 t 的长度时说明遍历结束且 s 不是 t 的子序列返回 false。当指针 i 指向的字符不等于指针 j 指向的字符指针 j 后移。当指针 i 指向的字符等于指针 j 指向的字符指针 i 和 j 同时后移。
最后遍历完字符串 s 的时候退出循环则代表 s 是 t 的子序列返回true。 三、代码
3.1 方法一双指针
3.1.1 Java易懂版
class Solution {public boolean isSubsequence(String s, String t) {int i 0, j 0;int n1 s.length(), n2 t.length();while (i n1) {if (j n2) return false;if (s.charAt(i) ! t.charAt(j)) {j;} else if (s.charAt(i) t.charAt(j)) {i;j;}}return true;}
}
3.1.2 Java优化版
class Solution {public boolean isSubsequence(String s, String t) {int i 0, j 0;int n1 s.length(), n2 t.length();while (i n1) {if (j n2) return false;if (s.charAt(i) t.charAt(j)) {i;}j;}return true;}
}
3.1.3 C版本
#include string
using namespace std;class Solution {
public:bool isSubsequence(string s, string t) {int i 0, j 0;int n1 s.length(), n2 t.length();while (i n1) {if (j n2) return false;if (s[i] t[j]) {i;}j;}return true;}
};3.1.4 Python版本
class Solution {public boolean isSubsequence(String s, String t) {int i 0, j 0;int n1 s.length(), n2 t.length();while (i n1) {if (j n2) return false;if (s.charAt(i) t.charAt(j)) {i;}j;}return true;}
}
3.1.5 Go版本
func isSubsequence(s string, t string) bool {i, j : 0, 0n1, n2 : len(s), len(t)for i n1 {if j n2 {return false}if s[i] t[j] {i}j}return true
}四、复杂度分析
4.1 方法一双指针
时间复杂度O(nm)其中 n 为 s 的长度m 为 t 的长度。每次无论是匹配成功还是失败都有至少一个指针发生右移两指针能够位移的总距离为 nm。空间复杂度O(1)。
