我要招人

去企业版

首页 > 试题广场 >

判断是不是子字符串

[编程题]判断是不是子字符串

热度指数：5285 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串 s和 t ，判断 s是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度n ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入描述:

共两行，第一行为字符串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

算法知识视频讲解

Java

已注销

    /**
     * 判断是不是子字符串
     *  双指针法
     * @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)

Java

螺狮粉在写日记

根据上面老哥的提示双指针做的，跑了几个用例没问题，有问题请指教

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)

Java

要讲武德

是我理解有问题么？用双指针一个p1从s开头每次向后移动，一个p2指向r开头，如果s[p1]==r[p2]，那么p2+=1;如果p2=r.length()则有，否则没有,空间复杂度o1，时间复杂度on,n为s.length()。

那么进阶是什么呢？进阶的空间变成on了？

发表于 2023-07-06 13:39:41 回复(1)

Java

牛客673795387号

  
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

燕赤侠

//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

FTL1ght

//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());
}
}

编辑于 2023-02-09 01:33:47 回复(0)

Java

冰虹醉月

在父串中组合子串

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)

Java

支金柱

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;
}
}
}

发表于 2022-08-26 11:10:17 回复(0)

Java

lyy0906

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);
        }
}
}

发表于 2021-03-11 15:33:49 回复(0)