精华内容
下载资源
问答
  • 例如:str1='ad',s='abcdef'则str1是s的子序列。str1='da',s='abcdef',str1则不是s的子序列。 子序列要求顺序与序列保持一致,可以不要求连续。 代码 def isSubsequence(s, str1): a, b = 0, 0 while a < ...

    前言

    首先说下什么是子序列。笔者不善于表达,还是举例说明吧。
    例如:str1='ad',s='abcdef'则str1是s的子序列。str1='da',s='abcdef',str1则不是s的子序列。
    子序列要求顺序与原序列保持一致,可以不要求连续。

    代码

    def isSubsequence(s, str1):
        a, b = 0, 0
        while a < len(s) and b < len(str1):
            if s[a] == str1[b]:
                a += 1
                b += 1
            else:
                a += 1
        if b == len(str1):
            return True
        else:
            return False
    print(isSubsequence('abcdef','da'))
    #output
    False
    

    值得注意的是,如果把字符串换成列表,则同样适用。

    展开全文
  • 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除...

    历次做算法题目,今天耗时最短。题目原链接leetcode

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
    
    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
    
    字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。
    
    示例 1:
    s = "abc", t = "ahbgdc"
    返回 true.
    
    示例 2:
    s = "axc", t = "ahbgdc"
    返回 false.
    
    

    解题逻辑,先用 s 的第一个字母和 t 的第一个字母比较,结果只有两种:
    如果不一样,就拿 s 的第一个字母和 t 的下一个字母比较,
    如果一样, 就拿s 的下一个字母和 t 的下一个字母比较

        public boolean isSubsequence(String s, String t) {
            char[] sChar = s.toCharArray();
            int sLen = s.length();
            char[] tChar = t.toCharArray();
            int tLen = t.length();
            int i = 0, j=0; // 初始下标
            while(i < sLen && j < tLen){
                if(sChar[i] == tChar[j]){
                    i++; // 相同,s的下标后移一位
                }
                j++; // 不论相同与否,j 的下标都后移一位
            }
            return i == sLen; 
        }
    

    官方题解中,除了双指针外,还给出了动态规划的解法,有兴趣的可以看一下。我觉得双指针已经完美解决问题,并且性能、内存消耗双百。动态规划有点大材小用了。
    在这里插入图片描述

    展开全文
  • 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除...

    原题链接

    不要自卑,去提升实力
    互联网行业谁技术牛谁是爹
    如果文章可以带给你能量,那是最好的事!请相信自己
    加油o~

    392.判断子序列

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
    字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

    示例1:

    s = “abc”, t = “ahbgdc”
    返回true

    示例2:

    s = “axc”, t = “ahbgdc”
    false

    解题思路:

    此道题和正常的模式匹配有所不同,要求相对位置不变即可,并不需要完全配对
    可以利用双指针进行模式匹配去做
    本题我用的是Java内置自带函数indexOf函数
    indexOf(char ch,int index)从主串进行查找ch,如果不存在,则返回-1,否则返回对应下标
    indexOf的查找效率比较高

    代码:

    /**
     *作者:魏宝航
     *2020年11月24日,下午20:02
     */
    public boolean isSubsequence(String s, String t) {
            int index=-1;
            for(char ch:s.toCharArray()){
                index=t.indexOf(ch,index+1);
                if(index==-1){
                    return false;
                }
            }
            return true;
        }
    

    执行结果:

    这里是引用

    展开全文
  • 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除...

    原题目

    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
    字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
    示例 1:
    s = “abc”, t = “ahbgdc”
    返回 true.
    示例 2:
    s = “axc”, t = “ahbgdc”
    返回 false.

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

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/is-subsequence

    题目大意

    在t字符串中按顺序找与s一一对应的字符,如果都找的到则为真,否则为假

    题目分析

    双指针法:定一个下标i代表s字符串的位置,再定一个下标j代表t字符串的位置,如果i下标下的字符值等于j下标下的字符值,则将i和j同时加一,移向下一位,如果不相等,则将j加一,表示拿下一个t中字符与s当前字符比较,直到s或t数组结束为止。如果i等于s字符串的长度则正确,表示已找到所有对应字符

    完整代码

    bool isSubsequence(char * s, char * t){
        int len1=strlen(s),len2=strlen(t);
        int i=0,j=0;
        while(s[i]&&t[j])
        {
            if(s[i]==t[j])
            {
             i++;
                j++;
            }
            else j++;
        }
        if(i==len1)return true;
        return false;
    }
    

    总结

    双指针法,直接一一比较,思路简单。

    展开全文
  • 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 &lt;=100)。 字符串的一个子序列是原始字符串...
  • 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除...
  • T1143 最长公共子序列

    2020-07-14 21:38:06
    子序列:一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。 case1: :暴力法 思想: 求最长公共子序列时,从左到...
  • 子串:小于等于原字符串长度由原字符串中任意个连续字符组成的子序列 回文:关于中间字符对称的...思想: 1)从最长的子串开始,遍历所有该原字符串的子串; 2)每找出一个字符串,就判断该字符串是否为回文; ...
  • 算法学习_字符匹配算法(BF,KMP,BM)

    千次阅读 2014-03-11 21:47:48
    转入正题,首先是问题定义,这里字符匹配指是连续子串匹配,而不是公共子序列。举例:asdfgge和dfg是匹配,因为asdfgge包含了dfg。问题就是判断子串A中是否包含子串B。 概要介绍了BF,BM,KMP三种字符...
  • LeetCode_392刷题笔记

    2020-07-07 21:48:48
    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除...
  • cout<<endl\texttt{cout<...两个串归并的时候通过判断第一个串的首字母加上第二串剩下的所有字母是否是原序列的子序列来确定下一位是否是第一个串的首字母。 CF1354G Find a Gift 注意到 k≤n2k.
  • 能否把只含T和M的字符串分成,若干个TMT的子序列原字符串长度是3的倍数 思路 我们看TMT这个串,M前面要有一个T,M后面也要有一个T,并且 cnt(T)=2*cnt(M) 那么我们从前往后遍历一遍,看每一个M的前面能否各自匹配到...
  • 像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时动作等,都可在本源码中得以体现。 Java编写显示器显示模式检测程序 2个目标文件 内容...
  • 像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时动作等,都可在本源码中得以体现。 Java编写显示器显示模式检测程序 2个目标文件 内容...
  • 实例142 判断是否为数字 实例143 判断用户名是否有效 5.3 日期时间处理 实例144 将指定日期字符串转换为Calendar对象 实例145 将Calendar对象转换为日期时间字符串 实例146 获得系统当前时间的字符串格式 实例...
  • 实例142 判断是否为数字 实例143 判断用户名是否有效 5.3 日期时间处理 实例144 将指定日期字符串转换为Calendar对象 实例145 将Calendar对象转换为日期时间字符串 实例146 获得系统当前时间的字符串格式 实例...
  • 高级Shell脚本编程

    2013-10-28 10:08:19
    字符串的前缀和后缀使用匹配模式 9-22. 使用declare来指定变量的类型 9-23. 间接引用 9-24. 传递一个间接引用给awk 9-25. 产生随机整数 9-26. 从一幅扑克牌中取出一张随机的牌 9-27. 两个指定值之间的...
  • 字符串是 Unicode 字符序列 8 位有符号整型 16 位有符号整型 32 位有符号整型 64 位有符号整型 示例 object o = null; 范围 string sbyte short int long string s = "hello"; sbyte val = 12; short val = 12; int...
  • 实例157 实现字符串的大小写转换 实例158 返回字符在字符串中出现的次数 实例159 返回字符串中的子串 实例160 删除字符串中的子串 实例161 查找并替换字符串 实例162 比较两个字符串 6.8 周期、日期查询 实例163 ...
  • 实例157 实现字符串的大小写转换 实例158 返回字符在字符串中出现的次数 实例159 返回字符串中的子串 实例160 删除字符串中的子串 实例161 查找并替换字符串 实例162 比较两个字符串 6.8 周期、日期查询 实例163 ...
  • 3.1.0 在函数内定义一个字符数组,用gets函数输入字符串的时候,如果输入越界,为什么程序会崩溃? 3.1.1 C++中引用与指针的区别 3.1.2 C/C++程序的内存分区 3.1.3 快速排序的思想、时间复杂度、实现以及优化方法...
  • 实例015 使用正则表达式检查字符串中重复出现词 实例016 使用正则表达式替换字符串 实例017 使用正则表达式拆分字符串 实例018 使用正则表达式验证输入字母 实例019 使用正则表达式验证中文汉字输入 实例020...
  • 实例015 使用正则表达式检查字符串中重复出现词 实例016 使用正则表达式替换字符串 实例017 使用正则表达式拆分字符串 实例018 使用正则表达式验证输入字母 实例019 使用正则表达式验证中文汉字输入 实例020...

空空如也

空空如也

1 2 3
收藏数 49
精华内容 19
关键字:

判断是否是原字符串的子序列