-
2020-09-05 13:24:52
方法1:双层循环,复杂度较高
int ifzixulie(char *s, int m, char *t, int n) { int i, j,k,f; k = 0; f = 0; for (i = 0; i < n; i++) for (j = k; j<m; j++) { if (t[i] == s[j]) { k = j + 1; f++; break; } } if (f!=n) return 0; else return 1; }
方法2:单层循环
int ifzixulie(char *s, int m, char *t, int n) { int i=0, j=0; while (i < n) { if (s[j] == t[i]) { i++; j++; if (i != n&&j == m) //特殊情况:adh不是ahd的子序列 return 0; } else { j++; if (j == m) return 0; } } return 1; }
主函数:
main() { char s[50], t[50] ; int m, n; scanf("%s", s); scanf("%s", t); m = strlen(s); n = strlen(t); if (ifzixulie(s, m, t, n)==0) printf("字符串t不是s的子序列"); else printf("字符串t是s的子序列"); }
更多相关内容 -
刷题03-判断是否是字符串的子序列
2020-08-04 22:41:04输入两个字符串 s 和 t,判断 t 是否是 s 的子序列。注意,子序列不要求在原字符串中是连续的,例如串 abc,它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。 输入描述 每个输入包含一个测试用例。每个测试...题目描述
扩展题目一------排序次数
输入两个字符串 s 和 t,判断 t 是否是 s 的子序列。注意,子序列不要求在原字符串中是连续的,例如串 abc,它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。
输入描述
每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。
输出描述
输出一行 “Yes” 或者 “No” 表示结果。
示例
输入
x.nowcoder.com ooo
输出
Yes
参考解法:
// 判断是否是子序列 // 子序列不要求在原字符串中是连续的 import java.util.Scanner; public class Demo_05 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char s1[] = sc.next().toCharArray(); char s2[] = sc.next().toCharArray(); int i=0,j=0; while (i<s1.length && j<s2.length){ // 关键在于把短字符串中的每一个字符都与长字符串相比较 // 相等就长度+1 // 最后看长度是否与短字符串相等 if(s1[i]==s2[j]){ i++; j++; }else i++; } if(j==s2.length) System.out.println("Yes"); else System.out.println("No"); } }
-
字符串 - 判断子序列
2020-07-27 11:27:11假如字符串 s 是 t 的子序列,那么可以删除 t 中的一些字符(也可以不删除),使得剩下的字符按原来的顺序排列得到的字符串等于s。 代码 LeetCode 392 代码比较简单,故不加赘述,记录本帖的意义在于防止日后卡壳。 ...定义
假如字符串 s 是 t 的子序列,那么可以删除 t 中的一些字符(也可以不删除),使得剩下的字符按原来的顺序排列得到的字符串等于s。
例题
LeetCode 392
代码比较简单,故不加赘述,记录本帖的意义在于防止日后脑子瓦特想不出来。时间复杂度:O(N + M),N和M为两个字符串的长度。
#include <iostream> #include <vector> #include <cstdio> #include <string> #include <map> #include <set> #include <cstring> #include <climits> #include <algorithm> #include <queue> #include <stack> #include <cmath> #include <cassert> using namespace std; class Solution { public: bool isSubsequence(string s, string t) { int len_s = s.size(); int len_t = t.size(); int idx = 0; for (char ch : t) { if (ch == s[idx]) { ++idx; if (idx >= len_s) break; } } return idx >= len_s; } };
-
【C】判断子字符串是否包含原字符串中(且返回子字符串在原字符串中出现的位置)
2018-12-03 01:22:49文章目录判断子字符串是否包含在原字符串中(且返回子字符串在原字符串中出现的位置)一、说明二、分析三、代码四、结果 判断子字符串是否包含在原字符串中(且返回子字符串在原字符串中出现的位置) 一、说明 &...判断子字符串是否包含在原字符串中(且返回子字符串在原字符串中出现的位置)
一、说明
此篇博文算是针对于是否包含字符串的加强版。
判断子字符串是否实包含原字符串中可以参考:此篇博文二、分析
测试比较字符串位置 说明: i:当前原字符串指针的位置 j:当前比较字符串指针的位置 weizhi:比较字符串第n次出现在原字符串的位置 一个中文字符占两个字节 第一种: 原字符串:贾房贾测贾 比较字符串:贾 原字符串 比较字符串 比较字符串第n次出现在原字符串的位置 i=2 j=2 weizhi=2 i=6 j=2 weizhi=6 i=10 j=2 weizhi=10 第二种: 原字符串:贾继康房贾继康测贾继康 比较字符串:贾继康 原字符串 比较字符串 比较字符串第n次出现在原字符串的位置 i=6 j=6 weizhi=2 i=14 j=6 weizhi=10 i=22 j=6 weizhi=18 第三种: 原字符串:测试贾继康房贾继康测贾继康侧设计费 比较字符串:贾继 原字符串 比较字符串 比较字符串第n次出现在原字符串的位置 i=8 j=4 weizhi=6 i=16 j=4 weizhi=14 i=24 j=4 weizhi=22
三、代码
/* 程序功能: 1:判断子字符串是否实现在原字符串中 2:且返回出现在原字符串所在的位置 */ #include <stdio.h> #include <string.h> #include <stdlib.h> //int is_in(char s, char c); int is_in(char *s, char *c, int location[]); int main() { char str[100] = "测试贾继康房贾继康测贾继康侧设计费"; char str1[100] = "贾继康"; //int *location = (int *)malloc(n * sizeof(int)); int loc[250] = {0}; int *location = loc; if (is_in(str, str1, location) == 1) { printf("原文件包含比较字符串\n"); for (int i = 0; i < sizeof(location); i++) { if (location[i] != 0) //待查字符串在原字符串中不为空 { printf("所在的位置:%d\n", location[i]); } } } else { printf("原文件不包含指定字符串\n"); } } // 子函数 int is_in(char *s, char *c, int location[]) { int i = 0, j = 0, flag = -1; int firstW = 0; int num = 0; while (i < strlen(s) && j < strlen(c)) // s:原字符串,c: 比较字符串 { if (s[i] == c[j]) // 指针所指位置的字符 { //如果字符相同则两个字符都增加 i++; j++; } else { i = i - j + 1; //主串字符回到比较 最开始比较的 后一个字符 j = 0; //字串字符重新开始 } if (j == strlen(c)) //如果匹配成功 { flag = 1; //字串出现 //i-strlen(c) 比较字符在原字符串中第一次出现的位置 printf("此时原字符串指针i的位置 %d\n", i); printf("此时比较字符串指针j的位置 %d\n", j); printf("比较字符串在原字符串中第一次出现的位置 %d\n\n", i - strlen(c) + 2); // i-strlen(c)+2 location[num] = i - strlen(c) + 2; num++; j = 0; continue; /* if (s[i] == '\0' || s[i] == '\n') { printf("结束\n"); break; } */ //return i-strlen(c)+2; //break; // 第一次出现了不能结束 } } return flag; //return i-strlen(c) +2; }
四、结果
五、补充
目的:int型数字转换为char型字符串
分析:
1、将所有的int型数字通过拼接,形成int型数组
2、再将int型数组转化为char型字符串 -
判断字符串str1是否是字符串s的子序列python3
2020-09-17 17:12:21前言 首先说下什么是子序列。...子序列要求顺序与原序列保持一致,可以不要求连续。 代码 def isSubsequence(s, str1): a, b = 0, 0 while a < len(s) and b < len(str1): if s[a] == str1[b]: -
求2个字符串的最长公共子序列和最长公共子字符串
2021-03-07 10:35:54一. 最长公共子序列定义:一个数列S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S... (Note: 不要求连续)判断字符串相似度的方法之一 - 最长公共子序列越长,越相似。思路:穷举方法... -
c语言判断字符串str1中含有字符串str2(是否为子串问题)
2020-12-20 13:57:44目录 一、可以用三种方式解决子串问题:函数strstr、...先举几个例子来说明一下什么样的字符串可以称作子串(区分大小写,假设字符串数组长度为20): 令str1[20]="dou LUO da lu"; 1.str2[20]="da l";是子串; 2. -
Unity3d c# 判断字符串是否是数字或字母
2020-03-26 15:09:29c# 有一个类,进行判断字符串是否是指定类型的。 string pattern=@"1+$"; System.Text.RegularExpressions.Regex regex=new System.Text.RegularExpressions.Regex(pattern); regex.IsMatch(“dfd@*fdf”);false; ... -
Python第四课(序列之字符串)
2021-03-06 18:48:09字符串的基本操作作为序列,序列的通用操作(索引、分片、加法、乘法、成员资格、长度、最大值、最小值)对于字符串都是适用的。但是字符串和元组一样都是不可变的,所以对字符串进行分片赋值是不合法的。格式化字符串... -
[LeetCode] Is Subsequence 判断一个字符串是否为另一个的子序列
2017-05-21 11:10:41声明:原题目转载自LeetCode,解答部分为原创 Problem : Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters... -
蓝桥杯每日练习(字符串哈希,最长公共子序列详解)
2022-03-23 11:10:00最长公共子序列是一个常见模型,换句话说,你掌握了这个模型就相当于会了很多题目。我是学习算法的小菜鸡,每天练习几个知识点,我们国赛见~ 今日题目 金币 模拟 题目描述 国王将金币作为工资,发放给忠诚的骑士。第... -
nyoj37回文字符串 最长公共子序列
2018-04-08 13:10:13当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。输入第一行给出整数N(0<N&... -
给定两个字符串a和b,判断b是否是a的子序列,例如a=”abndjs“,b=“and”则返回ture,如果b=”adn“,那么...
2016-10-19 22:46:27public class 判断是否是子串 { public static void main(String[] args) { boolean flag = isSubString("avdslg", "avdlg"); System.out.println(flag); } public static boolean isSubString(String a,... -
判断两个字符串的包含关系(直接比较法)
2021-03-06 02:08:3704-字符串全排列(非递归) 05-去除全排列中重复的序列 06-求两个字符串的最长公共子字符串(动态规划法) 07-反转字符串(交换变量法) 08-反转字符串(异或法) 09-反转字符串中的单词 10-判断两个字符串是否为... -
Python 序列(字符串、列表、元组)概述
2020-12-06 04:58:09在 Python 中有六种基本数据类型,即数字(包括整形、长整、浮点)、字符串、列表、元组、字典和布尔类型。其中,字符串、列表、元组被称之为序列。因为它们有着相同的访问模式,它们的每一个元素可以通过指定一个偏移... -
详解 Python 字符串(一):字符串基础
2021-01-16 20:59:45在 Python 中,字符串就是一串字符的组合,它是不可变的、有限字符序列,包括可见字符、不可见字符(如空格符等)和转义字符。Python 通过 str 类型提供大量方法来操作字符串,如字符串的替换、删除、截取、复制、... -
Chapter Three : Python 序列之字符串操作详解
2021-03-13 01:16:52目录一、字符串1. 字符串基础知识2. 字符串常见操作二、列表三、元组四、字典五、集合六、通用操作 一、字符串 字符串几乎是所有编程语言在项目开发过程中,涉及最多的一块内容。大部分项目的运行结果,都需要以文本... -
Leetcode刷题04-字符串
2022-02-21 18:57:23字符串基础知识、模式匹配、KMP、暴力算法、字符串习题、递归 -
python学习之字符串
2020-12-16 22:53:02字符串的“魔法"capitalize():首字母大写test = "aLex"# 首字母大写v= test.capitalize()print(v)lower():所有字符变为小写casefold():所有变小写,caseflod更牛逼,很多未知的相对应变小写#所有变小写,caseflod... -
python基础(四):元组(Tuple)、字典、字符串、序列
2020-04-23 20:49:34文章目录一、元组1、创建元组2、访问元组3、修改元组4、删除元组5、元组内置函数6、元组特点二、字符串1、去除空格2、连接字符串3、查找字符串4、比较字符串5、是否包含指定字符串6、字符串的长度7、字符串中大小写... -
python:字符串类型
2021-01-14 09:32:18字符串概念字符串:由单个字符组成的一个序列,字符串是一个不可变的类型形式:非原始字符串:单引号:单引号包起来的一段字符就是字符串双引号:和单引号一样三引号:三引号包括的字符串可以换行,保留所有空白字符... -
判断一个序列是否是另外一个序列的子序列的算法
2017-07-31 13:10:31从子序列中挨个找,找到一个之后,截取子序列和母序列之前的,然后继续递归自身 1.先分析下找不到的情况,如果母序列从头找到尾,也没有找到,则视为不是其子序列 2.继续分析找到的情况,如果找到之后,并且子序列... -
【不同的子序列问题】面试官写个字符串要我求有多少个“bigsai“,我懵了
2021-01-31 20:07:49字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是) 题目数据保证答案符合 32 位带符号整数... -
使用正则表达式判断字符串的第一个字符是不是字母 js
2021-05-08 14:46:16console.log("第一个字符串是字母") } else { console.log("第一个字符不是字母") } 正则表达式元字符 字符 描述 \ 将下一个字符标记为一个特殊字符、或一个原义字符、或一个 向后引用、或一个八进制转义... -
字符串中求最长数字串(两种题型)、包括标点的数字串、找最长的字符串、求最长连续子序列之和
2019-08-31 10:47:46读入一个字符串str,输出字符串str中的连续最长的数字串 输入描述: 个测试输入包含1个测试用例,一个字符串str,长度不超过255。 输出描述: 在一行内输出str中里连续最长的数字串。 输入 abcd12345ed125ss... -
【JAVA字符串最详细讲解】
2021-01-23 20:19:00JAVA字符串一级目录二级目录三级目录 一级目录 二级目录 三级目录 -
【JAVA】字符串操作 —字符串赋值、输出、合并、比较、查找、替换
2019-04-10 17:06:56一、前言 前面,我们整体学习了有关文件操作方面的知识,实现了检测、新建、修改文件并写入或者复制移动的操作。本次学习的是有关字符串方面的操作...字符串广泛应用 在Java 编程中,在 Java 中字符串属于对象,Jav... -
LeetCode 1055. 形成字符串的最短路径(贪心)
2020-08-06 20:05:47给定源字符串 source 和目标字符串 target,找出源字符串中能通过串联形成目标字符串的子序列的最小数量。 如果无法通过串联源字符串中的子序列来构造目标字符串,则返回 -1。 示例 1: 输入:source = "abc", ... -
回文字符串(最少添加多少个字符才能构成回文串,最长公共子序列)
2019-02-17 02:16:55回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符,使之变为回文字符串。 例如:abbc 添加2个字符可以变为 acbbca,也可以添加3个变为 abbcbba。方案1只需要添加2... -
字符串匹配问题:输入一个字符串,计算其中包含的‘连续’给定的子字符串最长的个数.
2017-12-28 21:58:36字符串匹配问题:输入一个字符串,计算其中包含的连续给定的子字符串的个数。例如输入字符串“ EFABCABCABCDABCDD ” , 给定子字符串“ ABC” ,输出是 3 。
收藏数
56,194
精华内容
22,477