【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)

简介: 【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
  • 作者简介:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名
  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论,💬支持博主,记得点个大大的关注,持续更新🤞


题目描述

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

你可以认为,如果 s 可以通过将 t 中的一些字符(也可以不删除)而不改变其余字符的相对位置来获得,那么 s 就是 t 的一个子序列。

原题:LeetCode 392

思路及实现

方式一:双指针法

思路

通过两个指针分别指向 st 的开头,然后逐个比较字符,如果相等则两个指针都向后移动一位,如果不等则只移动 t 的指针,直到 s 的指针指向末尾,则说明 st 的子序列。

代码实现

Java版本
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++; // s的指针向后移动
        }
        j++; // t的指针始终向后移动
    }
    return i == s.length(); // 如果s的指针走到了末尾,说明s是t的子序列
}

说明:通过双指针 ij 分别指向 st 的当前字符,并在满足条件时移动指针。

C语言版本
bool isSubsequence(char *s, char *t) {
    int i = 0, j = 0;
    while (s[i] && t[j]) {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return !s[i]; // 如果s的指针走到了末尾(即s[i]为'\0'),说明s是t的子序列
}

说明:C语言通过字符数组和指针实现与Java类似的逻辑。

Python3版本
def isSubsequence(s: str, t: str) -> bool:
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

说明:Python代码与Java和C语言类似,只是语法有所不同。

Golang版本
func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

说明:Golang的代码结构与其他语言类似,但语法和类型声明有所不同。

复杂度分析

  • 时间复杂度:O(m + n),其中 m 和 n 分别是字符串 st 的长度。两个指针至多遍历两个字符串各一次。
  • 空间复杂度:O(1),只使用了常量级别的额外空间。

复杂度分析

  • 时间复杂度:O(m + n),其中 m 和 n 分别是字符串 st 的长度。
  • 空间复杂度:O(k),其中 k 是字符串 t 中不同字符的数量。在最坏情况下,t 中的所有字符都不同,此时空间复杂度为 O(n)。
方式 优点 缺点 时间复杂度 空间复杂度
方式一 逻辑简单清晰,只需遍历一次字符串 无特别显著的缺点 O(m + n) O(1)

相似题目

相似题目 难度 链接
leetcode 115. 不同的子序列 困难 力扣-115
leetcode 300. 最长递增子序列 中等 力扣-300
leetcode 53. 最大子序和 简单 力扣-53

在解决“判断子序列”这类问题时,双指针法是一种非常高效且直观的方法,它能够直接通过比较字符的相对位置关系来判断一个字符串是否是另一个字符串的子序列,而无需使用额外的数据结构或复杂的算法。因此,在实际应用中,我们可以优先考虑使用双指针法来解决类似的问题。

欢迎一键三连(关注+点赞+收藏),技术的路上一起加油!!!代码改变世界

  • 关于我:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名),回复暗号,更能获取学习秘籍和书籍等
相关文章
|
13天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
15天前
|
机器学习/深度学习 人工智能 Java
Python和Java在哪些方面有所不同?
【7月更文挑战第2天】Python和Java在哪些方面有所不同?
12 1
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
24 2
|
1月前
|
Java 开发工具 开发者
【编程语言】Python平台化为何比Java差?
【编程语言】Python平台化为何比Java差?
22 1
|
15天前
|
数据采集 机器学习/深度学习 Java
Java和Python哪个更容易学?
【7月更文挑战第2天】Java和Python哪个更容易学?
13 0
|
21天前
|
开发框架 Java .NET
Java和Python的结合运用
Java和Python的结合运用
11 0
|
23天前
|
Java Python
分别使用python和java编写金字塔图形
分别使用python和java编写金字塔图形
8 0
|
2天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
4天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
17 7
|
1天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。

热门文章

最新文章