首页 > 试题广场 >

藏宝图

[编程题]藏宝图

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

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

输入描述:

每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述:

输出一行 “Yes” 或者 “No” 表示结果。

示例1

输入

nowcodecom
ooo

输出

Yes

算法知识视频讲解

Python

武者小小路

s = input()
t = input()
if t=='':
    print('Yes')
else:
    s_i = 0    #用来作为初始索引
    count = 0    #用来记录匹配上字符的个数
    for t1 in t:
        for i in range(s_i,len(s)):
            if s[i]==t1:
                #当i不等于最大的时候，初始索引应该是匹配到的后一位，即i+1
                if i!=len(s):
                    s_i = i+1
                count+=1
                break
    if count ==len(t):
        print('Yes')
    else:
        print('No')

发表于 2021-04-17 22:28:48 回复(0)

Python

王朕

s = list(input())
t = list(input())
no_flag = 0

for i in t:
    if i in s:
        _idx = s.index(i)
        for i in range(_idx+1):
            del s[_idx-i]
    else:
        no_flag = 1
        break

print('No' if no_flag else 'Yes')

思路：（开始以为题目中的子串和顺序无关，结果只通过了70%）通过遍历t中每一个元素是否在s中，若在则删除s中定位出之前的所有元素，以此来保证顺序

编辑于 2020-09-03 16:36:39 回复(0)

Python

沉静如渊

"""思路：
1.注意：t是s的子串时可以不连续，但顺序必须与s中字符的顺序一致，否则t不是s的子串
2.我的思路是将s和t解析成list，这时list中字符的顺序与原字符串中的顺序一致

3.每次比较之后，将已经比较的字符从sList中删除，不再二次比较，以此保证顺序一致性

代码有点多

"""

s=input()
t=input()
flag='Yes'
if(len(t)>len(s)):
    print('No')
else:
    if(s==t or len(t)==0):
        print('Yes')
    else:
        sList=list(s)
        tList=list(t)
        sL=sList[0:].copy()
        for i in range(len(tList)):    #遍历t字符串中的字符
            if (tList[i] not in sL):   #若字符不曾出现在s字符串剩余的字符中，则一定不是子串
                flag='No'
                break
            else:
                for j in range(len(sL)):
                    if(sL[j]==tList[i]):
                        sL=sL[j+1:]    #删除s中已遍历的字符
                        break
        #若t遍历完成后仍然题中满足要求，则t是s的子串
        print(flag)

通过

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例

编辑于 2019-08-27 20:15:29 回复(0)

Python

东不拉

s = input()
t = input()
#s = "x.nowcoder.com"
#t = "ooo"
N = "Yes"
for ss in t:
    if (ss in s) and (len(s) > 1):
        n = s.index(ss)
        s = s[n+1:]
    elif (ss in s) and (len(s) == 1):
        break
    else:
        N = "No"
        break

print(N)

编辑于 2018-09-26 16:37:45 回复(0)

Python

DJy201807201027569

1，取子序列N2第一个字符找出在原始序列N1的第一个的位置索引号保存在res[]，并且同时删除原始序列中
包括此位置之前的所有字符
2，继续第一步直道子序列查找完毕（中间出现子序列任何一个字符不存在于原始序列输出No结束）
3，将res升序排序后与原始res比较相等则输出Yes，否则输出No
import sys
N1=input()
N2=input()
def a(N1,N2):
    res=[]
    if N2 in N1:
        print('Yes')
    else:
        for i in N2:
            if(i in N1):
                n=N1.index(i)
                res+=[n]
                N1=N1[n+1:]
            else:
                print('No')
                return
        res1=res
        res.sort()
        if(res==res1):
            print('Yes')
        else:
            print('No')
    
a(N1,N2)

编辑于 2018-08-25 21:39:50 回复(0)

Python

外卖老谭

import sys
A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()
for i in A:
    if B == '':
        break
    if i == B[0]:
        B = B[1:]
if B == '':
    print('Yes')
else:
    print('No')

发表于 2018-08-11 12:47:04 回复(0)

Python

yzdeng

s=input()
t=input()
if not t:
    print ('Yes')
tmp=[-1]
flag=1
for i in t:
    a=s.find(i,tmp[-1]+1)
    tmp.append(a)
    if a ==-1:
        flag=0
        break
print ('Yes' if flag==1 else 'No')

发表于 2018-05-16 19:37:59 回复(0)

Python

离疏

s=input()
t=input()

n=len(s)
if t==[] or t==s:
    print('Yes')
if s==[] and t!=[]:
    print('No')
else:
    for i in t:
        if i in s:
            ans='Yes'
            j=s.index(i)
            s=s[j+1:n+1]
            continue
        else:
            ans='No'
            break
    print(ans)

发表于 2018-04-29 13:37:54 回复(0)

Python

华科平凡

python solution

思路：贪心。

s1,s2=input(),input()
for i in s1:
    if s2 and i==s2[0]:
        s2=s2[1:]
print("No" if s2 else "Yes")

发表于 2017-11-07 16:49:11 回复(4)

Python

人民的名义

Python:利用字符串的find函数：

string.find(str, beg=0, end=len(string))

检测 str 是否包含在 string 中，如果 beg 和 end 指定范围，则检查是否包含在指定范围内，如果是返回开始的索引值，否则返回-1

例如：

s='absdefgh' sub='asdf'

首先beg=index=0：sub第一个字符从最初的位置查找，若第一个字符存在s中，下标为index1=0,则下一个字符的位置应该在s[1:]范围内，因此查找的初始位置index=index1+1

若返回的是-1则说明当前字符不存在

s=input()
sub=input()
index=0
flag='Yes'
for i in sub:
    #利用 find函数 寻找子字符串中 每个字符的位置，其中index为初始位置，如果当前的字符存在，
    #则下一次寻找范围应该再当前字符位置后，故index=index+1
    index1=s.find(i,index,len(s))
    if index1!=-1:
        index=index1+1
    else:
        flag='No'
print(flag)

发表于 2017-10-18 18:07:59 回复(0)

Python

tb132123

import sys
x=raw_input()
y=raw_input()
for i in y:
id=x.find(i)
if id==-1:
print "No"
sys.exit()
x=x[id+1:]
print "Yes"

发表于 2017-09-22 19:33:40 回复(0)

Python

labulaka520

正则匹配

import re
str1 = input()
str2 = input()
item = ""
for i in str2:item +=".*"+i
item += ".*"
if re.search(item, str1):print("Yes")
else:print("No")

发表于 2017-09-10 15:12:11 回复(0)

Python

大中华王子

s = input("")
t = input("")
for index_t, item_t in enumerate(t):
    try:
        s_site = s.index(item_t)
        s = s[s_site+1:]
        if index_t==len(t)-1:
            print("Yes")
    except ValueError:
        print("No")
        break

发表于 2017-09-03 11:38:00 回复(0)

Python

沉漠

l = raw_input().strip()
s = raw_input().strip()

i = j = 0 while i<len(l) and j<len(s): if l[i] == s[j]:
        j+= 1  i+=1 if j == len(s): print "Yes" else: print "No"

发表于 2017-08-29 21:56:48 回复(0)

Python

Tudou啊

# 用正则表达式来做
import re
def test():
    origin = input()
    subString = input()
    pattern = ['.*']
    for word in subString:
        pattern.append(word+'.*')
    pattern = ''.join(pattern)
    pat = re.compile(pattern)
    if re.search(pat,origin):
        print("Yes")
    else:
        print("No")

test()

发表于 2017-08-11 13:04:46 回复(0)

Python

kelele67

def isSubstring():
    s = list(raw_input())
    t = list(raw_input())
    if t != '':
        for value in t:
            if value in s:
                s = s[s.index(value)+1:]
            else:
                return False
    return True

if isSubstring():
    print "Yes"
else:
    print "No"

还不错

发表于 2017-07-30 17:24:39 回复(0)

提交观点

问题信息

动态规划字符串

来自：网易2017内推笔试编...

难度：

16条回答 131收藏 23206浏览

通过挑战的用户

查看代码

刘礼金

2022-12-06 02:23:39
牛客54485...

2022-09-15 10:37:27
牛客82766...

2022-09-13 19:13:58
爱交友的少年在考古

2022-09-12 11:11:28
许你在右的年华

2022-09-11 18:15:51

藏宝图

输入描述:

输出描述:

输入

输出

python solution

思路：贪心。

正则匹配

问题信息

热门推荐

通过挑战的用户

相关试题