我要招人

去企业版

首页 > 试题广场 >

判断是不是子字符串

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

热度指数：7981 时间限制：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

算法知识视频讲解

JavaScript

渔樵_

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

// Write your code hereÏ

let tar = await readline();

let str = await readline();

let tarLen = tar.length

let matchLen = 0

let pre = 0

for (let i = 0; i < tar.length; i++) {

for (let j = pre; j < str.length; j++) {

if (tar[i] == str[j]) {

matchLen++

pre = j

break

}

console.log(tarLen == matchLen)

})();

发表于 2024-09-14 00:56:08 回复(0)

JavaScript

没有昵称可用

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

let data=[]

void async function () {

// Write your code here

while(line = await readline()){

data.push(line)

}

let len = data[0].length,str='',t=data[0],s=data[1].split('')

for(let i=0;i<len;i++){

let index = s.indexOf(t[i]);

if(index!==-1){

str+=t[i]

s.splice(0,index+1)

}

if(str === t){

console.log(true)

}else{

console.log(false)

}

}()

发表于 2023-04-06 13:14:54 回复(0)

JavaScript

小新9527

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const arr=[]
rl.on("line", function (line) {
    arr.push(line)
    if(arr.length===2){
        let s=arr[0]
        let t=arr[1]
        let str=''
        let index=0
        for(let i=0;i<s.length;i++){
            for(let j=index;j<t.length;j++){
                if(s[i]==t[j]){
                    index=j
                    str+=s[i]
                    break
                }
            }
        }
        console.log(str===s)
    }
});

发表于 2022-09-30 17:27:50 回复(0)

JavaScript

WD-Coke

let str2=readline()
let str=readline()
let arr=str.split('')
let arr2=str2.split('')
let key
for (let i=0;i<arr2.length;i++){
let a=arr.findIndex(item => {
return item === arr2[i]
})
if (a===-1){
key=false
break
}else {
key=true
arr.splice(0,a+1)
}
}
console.log(key)

发表于 2021-09-19 11:25:08 回复(0)

JavaScript

来个offerbei

// 思路：每寻找s中的下一位元素，都是在上一位已找到的元素的下一个下标开始找即可满足题意

var s = readline()

var t = readline()
var sArr = s.split('')
var tArr = t.split('')
const len = tArr.length
var j = 0
for(let i = 0;i<sArr.length;i++) {
let index = tArr.slice(j).indexOf(sArr[i])
if(index===-1) {
print(false)
break
} else {
index = index + j //由于是上面使用slice()截取了后面部分的数组寻找元素，所以找到的该元素是在原数组的index + j处
if(i===sArr.length-1) {
print(true)
break
}
if(j>=len - 1&&i!==sArr.length-1) {
print(false)
break
}
j = index + 1
}
}

发表于 2021-08-26 09:59:13 回复(0)

JavaScript

张煜豪

function decide(str1, str2) {
  str2 = str2.split('')
  str1 = str1.split('')
  if (str2.length < str1.length) return false;
  let num = str1.length
  let first = str1.shift()
  let counter = 0
  for (let i = 0; i < str2.length; i++) {
    if (first === str2[i]) {
      counter++;
      first = str1.shift()

    }
  }
  return num === counter
}

发表于 2021-03-22 11:18:33 回复(0)