首页 > 试题广场 >

藏宝图

[编程题]藏宝图

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

华科平凡

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)

仪小贱

#include<iostream>
#include<string>
using namespace std;

int main(){
	string str;
	while (cin >> str){
		string str1;
		cin >> str1;
		int a=0, b = 0;
		while (a < str.length()){
			if (str[a++] == str1[b])
				b++;

		}
		if (b == str1.length())
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}

}

发表于 2016-08-26 21:40:36 回复(10)

SoyLee

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()){
			char[] arr1 = sc.next().toCharArray();
			char[] arr2 = sc.next().toCharArray();
			int i=0,j=0;
			while (j<arr2.length && i<arr1.length){
				if(arr1[i] == arr2[j]){
					i++;
					j++;
				}//if
				else{
					i++;
				}//else
			}
			if(j==arr2.length)
				System.out.println("Yes");
			else
				System.out.println("No");
		}//while
		sc.close();
	}
}

发表于 2017-08-26 11:59:24 回复(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)

owner

import java.util.*;
public class Main {
	
	public static final void main(String[] args){
		Scanner scan=new Scanner(System.in);
		while(scan.hasNext()){
			String str1=scan.nextLine();
			String str2=scan.nextLine();
			boolean result=isContain(str1,str2);
			if(result){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}
		scan.close();
	}
	
	public static boolean isContain(String str1,String str2){
		for(int i=0,index=0;i<str1.length();i++){
			if(str1.charAt(i)==str2.charAt(index)){
				index++;
				if(index==str2.length()){
					return true;
				}
			}
		}
		return false;
	}
	

}

发表于 2016-08-28 16:03:29 回复(1)

菜鸟四号

#include <bits/stdc++.h>
using namespace std;
int main() {
    char s1[10000],s2[10000];
    scanf("%s %s",s1,s2);
    int len1=strlen(s1),len2=strlen(s2),t=0,cnt=0;
    for(int i=0; i<len2; i++) {
        for(int j=t; j<len1; j++) {
            if(s1[j]==s2[i]) {
                t=j+1,cnt++;
                break;
            }
        }
        if(cnt==len2) {
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(cnt!=len2)
        cout<<"No"<<endl;
    return 0;
}

发表于 2017-08-09 16:28:19 回复(1)

C/C++

卡玛酱

#include <iostream>
#include <string>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	for(int i=0;i<t.size();i++){
		size_t found=s.find(t[i]);
		if(found==s.npos){
			cout<<"No"<<endl;
			return 0;
		}else{
			s=s.substr(found+1);
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

发表于 2017-08-24 21:32:26 回复(1)

Java

leemotion

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
     Scanner sc=new Scanner(System.in);
     String str=sc.nextLine();
     String aim=sc.nextLine();
     System.out.print(flag(str,aim,0,"")?"Yes":"No");
    }
    public static boolean flag(String str,String aim,int i,String sum){
        if(i==str.length()){
        return sum.equals(aim);
        }
        return flag(str,aim,i+1,sum)||flag(str,aim,i+1,sum+str.charAt(i));
        
    }    
}

发表于 2019-02-23 13:52:19 回复(1)

牵着蜗牛

import java.util.Scanner;
public class Main{
    public static void main(String []args) {
        Scanner sc = new Scanner(System.in);
        String s=sc.nextLine();
        String t=sc.nextLine();
        if(check(s,t)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
    public static boolean check(String s,String t){
        char []arr=t.toCharArray();
        for(int i=0;i<arr.length;i++){
            if(s.indexOf(arr[i])==-1)   return    false;
            if(s.indexOf(arr[i])!=-1) {
                s = s.substring(s.indexOf(arr[i]) + 1);
            }
        }
        return true;
        
    }
}

编辑于 2018-05-31 20:35:28 回复(0)

GrantLeung

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int main()
{
    char a[12],b[12],t=0;
    int p=0;
    cin>>a>>b;
    for(int i=0;i<strlen(b);i++)
    {
        for(int j=t;j<strlen(a);j++)
        {
            if(a[j] == b[i])
            {
                p++;//匹配成功则p加1
                t = j+1;//下次接着这次检查到的a的位置继续检查下去
                break;//跳出循环，检查b的下一个字符
            }
        }
    }
    if(p == strlen(b))//只要b全部字符都能匹配到，则证明b是a的子集
        cout<<"Yes";
    else
        cout<<"No";
}

发表于 2018-04-02 11:07:00 回复(0)

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)

脑回路不正常患者

典型的最长非连续公共子串查找，动态规划的基础题。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String origin = scan.nextLine();
		String target = scan.nextLine();
		System.out.println(get_treasure(origin, target));
		scan.close();
	}

	private static String get_treasure(String origin, String target) {
		int[][] dp = new int[origin.length() + 1][target.length() + 1];
		for(int i = 1; i <= origin.length(); i++){
			for(int j = 1; j <= target.length(); j++){
				if(origin.charAt(i - 1) == target.charAt(j - 1)){
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else{//如果不等，则取前三种公共子串长度中的最大长度作为当前子串的最大长度
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][ j - 1]);
				}
			}
		}
		return dp[origin.length()][target.length()] == target.length() ? "Yes" : "No";
	}

	private static int max(int i, int j, int k) {
		return (i > j) ? ( i > k ? i : k) : (j > k ? j : k);
	}

}

发表于 2017-09-05 11:55:54 回复(1)

辣鸡_本科生

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int ns=s.size(),nt=t.size();
    int i=0,j=0;
    while(i<ns&&j<nt)
        if(s[i]==t[j]){
            i++;
            j++;
        }
        else
            i++;
    if(j==nt)
        cout<<"Yes";
    else
        cout<<"No";
}

发表于 2018-11-21 12:51:09 回复(0)

RicharthLee

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s1 = sc.nextLine();
    String s2 = sc.nextLine();
    sc.close();        
    boolean f = true;
    int len = s2.length();

    for (int i = 0 ; i < len ; i++) {
        if(s1.indexOf(s2.substring(0, 1)) != -1) {
            s1 = s1.substring(s1.indexOf(s2.substring(0, 1))+1);
            s2 = s2.substring(1);
        }
        else {
            f = false;
        }
    }

    if(f) {
        System.out.println("yes");
    }
    else {
        System.out.println("no");
    }
}

发表于 2018-08-26 19:23:11 回复(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)

©☞陨辰☜℡

#include<iostream>
#include<string>
using namespace std;

int main()
{
string s,t;
while(cin>>s>>t)
{
int l=s.length();
int k=t.length();
int j=0;
for(int i=0;i<l;i++)
{
while(s[i]==t[j]&&i<l)
{
j+=1;
break;
}
}
j==k?cout<<"Yes":cout<<"No";
// cout<<k<<j;
}
return 0;
}

发表于 2018-08-21 22:14:15 回复(0)

该用户名无法显示

var s=readline();
var t=readline();
var add=".*";
var str_reg="";
for(var i=0;i<t.length;i++){
	if(/[.*+?()$^{}]/g.test(t[i])){
		str_reg+=add+"\\"+t[i];
	}else{
		str_reg+=add+t[i];
	}	
}
str_reg=str_reg+add;
var reg=new RegExp(str_reg,"g")
if(reg.test(s)){
	print("Yes");
}else{
	print("No");
}

发表于 2018-07-23 21:04:08 回复(0)

zcenao21

动态规划简单题目

#include 
#include 
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int i = 0, j = 0;//i,j分别表示当前所在字符位置
    while (i<s.length()){
        if (s[i] == t[j]){
            i++; j++;
        }
        else{//s[i]!=t[j]
            i++;
        }
    }

    cout << (j == t.length() ? "Yes" : "No");
    return 0;
}

编辑于 2018-07-22 15:32:44 回复(0)

Java

黄小斜

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        System.out.println(sub(s1, s2));
    }

    public static String sub(String s1, String s2) {
        int i = 0,j = 0;
        int start = 0;
        while (start < s1.length()) {
            //s1从第start个元素开始找s2。因为子串可能从任意位置开始匹配
            j = start;
            i = 0;
            //开始匹配
            while (i < s2.length() && j < s1.length()) {
                if (s1.charAt(j) == s2.charAt(i)) {
                    i++;
                    j++;
                } else {
                    j++;
                }
            }
            start ++;
            if (i == s2.length()) {
                return "Yes";
            }
        }
        return "No";
    }
}

发表于 2018-05-19 18:07:40 回复(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)

提交观点

问题信息

动态规划字符串

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

难度：

244条回答 131收藏 22432浏览

通过挑战的用户

查看代码

刘礼金

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

思路：贪心。

正则匹配

动态规划简单题目

问题信息

热门推荐

通过挑战的用户

相关试题