Leetcode 每日一题 392.判断子序列

news/2024/11/20 20:11:48/

问题描述

给定两个字符串 st,我们需要判断 s 是否为 t 的子序列。子序列是指在不改变剩余字符相对位置的情况下,通过删除 t 中的一些(或不删除)字符形成的新字符串。

示例

  • 输入:s = "abc", t = "ahbgdc"
    输出:true
    解释:"abc""ahbgdc" 的一个子序列,因为可以删除 "ahbgdc" 中的 "h", "g", "d" 得到 "abc"

  • 输入:s = "axc", t = "ahbgdc"
    输出:false
    解释:"axc" 不是 "ahbgdc" 的子序列,因为 "ahbgdc" 中不存在 "x"

算法分析

对于这个问题,我们可以采用双指针的方法来解决。我们维护两个指针 ij,分别指向 st 的当前比较位置。遍历 t 的同时,检查当前字符是否与 s 中的当前字符相等,如果相等,则两个指针同时前进;如果不相等,则只有 t 的指针前进。如果 s 的指针 i 先到达 s 的末尾,说明 s 已经完全匹配了 t 中的子序列,返回 true;否则返回 false

代码实现

 

java

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

进阶问题

如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,我们需要依次检查它们是否为 T 的子序列。在这种情况下,我们可以采取以下策略:

  1. 预处理 T:首先,我们可以对 T 进行预处理,建立一个字符到索引列表的映射,这样对于每个 Si,我们可以直接查找每个字符在 T 中的位置,而不是每次都遍历 T

  2. 并行处理:考虑到 k 的规模非常大,我们可以利用并行计算来加速处理过程。将 S 分成多个批次,每个批次由多个 Si 组成,然后在不同的处理器或服务器上并行处理这些批次。

  3. 缓存结果:对于重复出现的 Si,我们可以缓存它们的结果,避免重复计算。

  4. 优化存储:考虑到 k 的规模,我们需要优化存储方案,可能需要使用分布式存储系统来存储所有的 Si 和它们的结果。

  5. 算法优化:对于每个 Si 的检查,我们可以使用更高效的算法,比如后缀数组或后缀树,这些数据结构可以更快地判断子序列。


http://www.ppmy.cn/news/1548561.html

相关文章

C语言实例_1之从4个不重复的数中,找出3个不重复的数的集合

题目 有 1、2、3、4 四个数字&#xff0c;能组成多少个互不相同且无重复数字的三位数&#xff1f;都是多少&#xff1f; 分析 可填在百位、十位、个位的数字都是 1、2、3、4&#xff0c;组成所有的排列后再去掉不满足条件的排列。 实例代码 #include<stdio.h> // 程…

如何在K8s集群中管理与使用GPU

背景 随着人工智能的兴起&#xff0c;GPU作为重要的智算算力类型愈发受到重视&#xff0c;而Kubernetes&#xff08;k8s&#xff09;作为业界主流的集群管理系统&#xff0c;如何方便管理、使用GPU也是其需要解决的一大问题&#xff0c;故此收集整理了K8s管理与使用GPU的相关资…

基于YOLOv8深度学习的婴儿情绪状态检测系统(PyQt5界面+数据集+训练代码)

婴儿的情绪状态是其表达健康状况、情感需求以及与外界互动的重要方式&#xff0c;准确识别婴儿的情绪对父母和看护者理解其需求具有关键意义。然而&#xff0c;由于婴儿语言能力的缺乏&#xff0c;他们通常通过面部表情、动作和哭声等非语言行为来表达情绪&#xff0c;因此需要…

Qt小知识-Q_GLOBAL_STATIC

你还在为创建全局静态对象烦恼嘛&#xff0c;它来了&#xff01;它来了&#xff01; qt5提供了两个宏定义Q_GLOBAL_STATIC和Q_GLOBAL_STATIC_WITH_ARGS来实现。可以创建一个全局静态对象&#xff0c;对象在第一次使用时初始化自身&#xff0c;这意味着它不会增加应用程序或库的…

Gin 中自定义控制器

1、控制器分组 当我们的项目比较大的时候有必要对我们的控制器进行分组 新建 controller/admin/NewsController.go package admin import ( "net/http" "github.com/gin-gonic/gin" )

kafka不同的消费场景

kafka常见的消费场景 从头开始消费从最新偏移量消费从特定时间戳偏移量消费 kafka消费场景详细配置方法 消费模式配置参数场景从头开始消费scan.startup.modeearliest-offset回放所有历史数据从最新偏移量消费scan.startup.modelatest-offset实时消费新数据从特定时间戳消费…

LLM学习笔记(5)微调 Fine-tuning

什么是微调&#xff08;Fine-tuning&#xff09;&#xff1f; 微调&#xff08;Fine-tuning&#xff09;是指在预训练模型&#xff08;如 GPT&#xff09;基础上&#xff0c;通过加入特定的数据对模型进行进一步训练&#xff0c;以优化其在某一特定任务或领域上的表现。它的主…

0x00基础算法 -- 0x06 倍增

资料来源&#xff1a;算法竞赛进阶指南活动 - AcWing 1、倍增 倍增&#xff1a;"成倍增长"&#xff0c;指进行递推时&#xff0c;如果状态空间很大&#xff0c;通常的线性递推无法满足时间和空间复杂度的要求&#xff0c;就可以通过成倍增长的方式&#xff0c;只递推…