你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度n ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：时间复杂度%5C)
，空间复杂度
[编程题]判断是不是子字符串
- 热度指数：7912 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定两个字符串 s和 t ，判断 s是否为 t 的子序列。
输入描述:
共两行，第一行为字符串s, 第二行为字符串t
字符串t的长度 1<=n<=500000
字符串s的长度 1<=m<=100
输出描述:
输出true或者是false，true表示是s是t的子序列，false表示s不是t的子序列
示例1
输入
abc ahbgdc
输出
true
示例2
输入
axc ahbgdc
输出
false
public boolean isStr(String s, String t){
if(s.isEmpty())
return true;
int index = 0;
for (char c : t.toCharArray()) {
if (s.charAt(index)==c&&++index==s.length())
return true;
}
return false;
}
编辑于 2025-04-25 17:16:42
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
char[] subStrArr = in.nextLine().toCharArray();
char[] mainStrArr = in.nextLine().toCharArray();
int i = 0, j = 0;
while (i < subStrArr.length && j < mainStrArr.length) {
if (subStrArr[i] == mainStrArr[j]) i++;
j++;
}
if (i == subStrArr.length)
System.out.println("true");
else
System.out.println("false");
}
}
}
编辑于 2025-03-29 14:13:17
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.next();
String t = input.next();
if (s.length() > t.length()) {
System.out.print("false");
}
else {
int si = 0, ti = 0;
while (si < s.length() && ti < t.length()) {
if (s.charAt(si) == t.charAt(ti)) {
si++;
}
ti++;
}
if (si == s.length()) {
System.out.print("true");
} else {
System.out.print("false");
}
}
}
} 双指针，字符匹配时向后移动s的指针，且无论是否匹配，都移动 t 的指针；最后s的指针达到了s的末尾，证明s是t的子序列
发表于 2025-02-13 21:38:20
回复(0)
import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String s = in.nextLine();
if (s == null || "".equals(s.trim())) {
System.out.println("false");
return;
}
String t = in.nextLine();
if (t == null || "".equals(t.trim())) {
System.out.println("false");
return;
}
if (s.length() > t.length()) {
System.out.println(false);
return;
}
HashMap<Integer, ArrayList<Integer>> locMap = new HashMap<>(26);
for(int i = 0 ;i < t.length(); i++) {
int index = t.charAt(i) - 'a';
ArrayList<Integer> tmp = locMap.get(index);
if (tmp == null) {
tmp = new ArrayList<>();
locMap.put(index, tmp);
}
tmp.add(i);
}
System.out.println(location(0, 0 ,s,locMap));
}
public static boolean location(int start,int index, String s, HashMap<Integer, ArrayList<Integer>> locMap) {
if (index >= s.length()) return true;
ArrayList<Integer> locList = locMap.get(s.charAt(index) - 'a');
if (locList == null) return false;
for(int i = 0 ; i < locList.size(); i++) {
if (locList.get(i) >= start && location(locList.get(i) + 1, index + 1, s, locMap)) return true;
}
return false;
}
}
import java.util.HashMap;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String s = in.nextLine();
if (s == null || "".equals(s.trim())) {
System.out.println("false");
return;
}
String t = in.nextLine();
if (t == null || "".equals(t.trim())) {
System.out.println("false");
return;
}
if (s.length() > t.length()) {
System.out.println(false);
return;
}
HashMap<Integer, ArrayList<Integer>> locMap = new HashMap<>(26);
for(int i = 0 ;i < t.length(); i++) {
int index = t.charAt(i) - 'a';
ArrayList<Integer> tmp = locMap.get(index);
if (tmp == null) {
tmp = new ArrayList<>();
locMap.put(index, tmp);
}
tmp.add(i);
}
System.out.println(location(0, 0 ,s,locMap));
}
public static boolean location(int start,int index, String s, HashMap<Integer, ArrayList<Integer>> locMap) {
if (index >= s.length()) return true;
ArrayList<Integer> locList = locMap.get(s.charAt(index) - 'a');
if (locList == null) return false;
for(int i = 0 ; i < locList.size(); i++) {
if (locList.get(i) >= start && location(locList.get(i) + 1, index + 1, s, locMap)) return true;
}
return false;
}
}
发表于 2025-02-10 18:48:22
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String strSon = in.nextLine();
String strFather = in.nextLine();
System.out.println(strContainJuDge(strSon, strFather));
}
public static Boolean strContainJuDge(String strSon, String strFather) {
//第一步，判断子串里的所有字符是否都在父串中有
if (strSon.length() == 0 || strFather.length() == 0 ||
strFather.length() < strSon.length()
|| strFather.length() > 500000 || strSon.length() > 100) {
return false;
}
char[] sonCharArray = strSon.toCharArray();
int y = 0;
for (int i = 0; i < sonCharArray.length; i++) {
int x = strFather.indexOf(sonCharArray[i], y);
if (x == -1) {
return false;
} else {
y = x;
}
}
return true;
}
}
发表于 2024-10-04 18:09:10
回复(0)
《程序员面试金典》一次编辑，双指针。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String subString = in.next();
String fullString = in.next();
System.out.println(isSubsequence(subString, fullString));
}
public static boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
int m = s.length(), n = t.length();
while (i < m && j < n) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == m;
}
}
发表于 2024-08-22 16:49:19
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String sub = in.nextLine();
String str = in.nextLine();
int index = 0;
for (int i = 0; i < sub.length(); i++) {
for (; index < str.length(); index++) {
if (sub.charAt(i) == str.charAt(index)) {
if (i == sub.length() - 1) {
System.out.println(true);
return;
}
index++;
break;
}
}
}
System.out.println(false);
}
}
编辑于 2024-06-05 14:16:32
回复(0)
/**
* 判断是不是子字符串
* 双指针法
* @return
*/
public static boolean isChildStr(String longStr, String shortStr) {
int ss = 0,ls = 0;
while (ls < longStr.length()){
if (shortStr.charAt(ss) == longStr.charAt(ls)){
if (ss == shortStr.length()-1) return true;
ss++;
ls++;
}else {
ls++;
}
}
if (ss == shortStr.length()-1){
return longStr.charAt(longStr.length()-1) == shortStr.charAt(shortStr.length()-1);
}else
return false;
}
编辑于 2024-04-20 13:48:27
回复(0)
根据上面老哥的提示双指针做的，跑了几个用例没问题，有问题请指教
import java.util.Scanner;
public class Main21 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String t = sc.nextLine();
String s = sc.nextLine();
int p1=0;
int p2=0;
for(int i=0;i<t.length();i++){
if(t.charAt(p1)==s.charAt(p2)){
p1++;
p2++;
}else if(t.charAt(p1) != s.charAt(p2)) p1++;
if(p1>t.length()||p2>s.length()){
break;
}
}
System.out.println(p2>s.length()-1);
}
}
发表于 2024-04-16 18:27:34
回复(0)
public static void main(String[] args) { Scanner in =new Scanner(System.in); String s=in.nextLine(); String k=in.nextLine(); int i=0,j=0,sum=0; if(s.length()>k.length()){ System.out.println(false); return; } while (i<s.length()&&j<k.length()){ if(s.charAt(i)==k.charAt(j)){ i++; sum++; } j++; } if(sum==s.length()){ System.out.println(true); }else { System.out.println(false); } }
发表于 2023-07-01 08:50:40
回复(0)
//java
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String t = in.nextLine();
int begin = 0;
String a = "";
for (int i = 0; i < s.length(); i++) {
a = s.charAt(i) + "";
begin = t.indexOf(a, begin);
if (begin == -1) {
System.out.println("false");
return;
}
}
System.out.println("true");
}
}
发表于 2023-04-07 16:34:05
回复(0)
//Java 屎山？
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String child = in.nextLine();
String father = in.nextLine();
int count = 0;
int index = 0;
for (int i = 0;i<child.length();i++) {
if (father.substring(index).contains(child.substring(i,i+1))){
index += father.substring(index).indexOf(child.substring(i, i + 1));
count++;
}else{
break;
}
}
System.out.println(count == child.length());
}
}
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String child = in.nextLine();
String father = in.nextLine();
int count = 0;
int index = 0;
for (int i = 0;i<child.length();i++) {
if (father.substring(index).contains(child.substring(i,i+1))){
index += father.substring(index).indexOf(child.substring(i, i + 1));
count++;
}else{
break;
}
}
System.out.println(count == child.length());
}
}
编辑于 2023-02-09 01:33:47
回复(0)
在父串中组合子串
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("input zi chuan");
String childrenString = input.next();
System.out.println("input fu chuan");
String superString = input.next();
System.out.println(panduan(childrenString,superString));
}
public static boolean panduan(String zc, String fc){
String s = fc;
for(int i =0 ; i < zc.length();i++){
char ch = zc.charAt(i);
//在父串中组合子串
s = s.substring(s.indexOf(ch));
if(s.indexOf(ch) == -1 )
return false;
}
return true;
}
}
发表于 2022-09-01 16:20:33
回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
String s = "";
String t = "";
if (scanner.hasNext()) {
s = scanner.next();
}
if (scanner.hasNext()) {
t = scanner.next();
}
if (s.length()>t.length()){
System.out.println(false);
return;
}
if(s.length() == t.length()){
if(s.equals(t)){
System.out.println(true);
}else{
System.out.println(false);
}
return;
}
int count=0;
for (int i=0;i<s.length();i++){
if (t.length()<=count){
System.out.println(false);
return;
}
for (int count1 = count;count1<t.length();count1++){
if (t.charAt(count1)==s.charAt(i)){
count = count1+1;
break;
}
if (count1 == t.length()-1){
System.out.println(false);
return;
}
}
}
System.out.println(true);
return;
}
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
String s = "";
String t = "";
if (scanner.hasNext()) {
s = scanner.next();
}
if (scanner.hasNext()) {
t = scanner.next();
}
if (s.length()>t.length()){
System.out.println(false);
return;
}
if(s.length() == t.length()){
if(s.equals(t)){
System.out.println(true);
}else{
System.out.println(false);
}
return;
}
int count=0;
for (int i=0;i<s.length();i++){
if (t.length()<=count){
System.out.println(false);
return;
}
for (int count1 = count;count1<t.length();count1++){
if (t.charAt(count1)==s.charAt(i)){
count = count1+1;
break;
}
if (count1 == t.length()-1){
System.out.println(false);
return;
}
}
}
System.out.println(true);
return;
}
}
}
发表于 2022-08-26 11:10:17
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String son = scanner.nextLine();
String mother = scanner.nextLine();
int i, j;
for(i = 0, j = 0; i < mother.length() && j < son.length(); i++) {
if(mother.charAt(i) == son.charAt(j)) {
j++;
}
}
if(j == son.length()) {
System.out.println(true);
}else {
System.out.println(false);
}
}
}
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String son = scanner.nextLine();
String mother = scanner.nextLine();
int i, j;
for(i = 0, j = 0; i < mother.length() && j < son.length(); i++) {
if(mother.charAt(i) == son.charAt(j)) {
j++;
}
}
if(j == son.length()) {
System.out.println(true);
}else {
System.out.println(false);
}
}
}
发表于 2021-03-11 15:33:49
回复(0)
问题信息
通过挑战的用户
-
2023-03-14 12:13:27
-
2023-03-13 19:47:03
-
2023-03-12 11:12:22 -
2023-03-11 21:08:10 -
2023-03-11 20:49:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
