首页 > 试题广场 >

藏宝图

[编程题]藏宝图

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

算法知识视频讲解

Java

pein531

不用动态规划，直接双指针跑起来就行。两个指针p1和p2初始分别指向两个字符串s和t的起始字符，如果相等，两个指针都移动，否则只移动p1。最后检查一下p2是不是移动到了t.length就行，如果到了就说明所有t中的字符都在s中按照t字符串的字符顺序出现过了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        char[] t = br.readLine().toCharArray();
        int p1 = 0, p2 = 0;
        while(p1 < s.length && p2 < t.length){
            if(s[p1] == t[p2]){
                p1 ++;
                p2 ++;
            }else{
                p1 ++;
            }
        }
        System.out.println(p2 == t.length? "Yes": "No");
    }
}

编辑于 2022-03-22 16:08:10 回复(0)

Java

jsysisnz

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s=sc.next();
            String t=sc.next();
            int j=0;
            for(int i=0;i<s.length();i++){
                while(j<t.length()&&s.charAt(i)==t.charAt(j)){
                    j++;
                    i++;
                }
            }
            if(j==t.length())
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }
}

发表于 2021-08-31 15:10:52 回复(0)

Java

lmz9509

谁能救救孩子，这个怎么不行呢？

import java.util.*;
public class test5{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            String str = input.next();
            String substr = input.next();
            List<String> list = new ArrayList<String>();
            List<String> sublist = new ArrayList<>();
            list.add(str);
            sublist.add(substr);
            //System.out.println(list);
            //System.out.println(list.indexOf(sublist.get(0)));
            for(int i =0;i<sublist.size();i++){
                //String ch = String.valueOf(substr.charAt(i));
                int index = list.indexOf(sublist.get(i));
                System.out.println(index);
                if(index!=-1){
                    list.set(index," ");
                    //list.remove(list.indexOf(ch));
                    //System.out.println(list.indexOf(ch));
                }else{
                    System.out.println("No");
                    return;
                }
            }
            System.out.println("Yes");
        }
    }
}

发表于 2020-05-02 17:03:37 回复(0)

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)

Java

javaxiao_White

package xiaozhao;

import java.util.Scanner;

public class 藏宝图 {
public static void main(String args[]) {
new 藏宝图().run();

}
public void run() {
int count=0;
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
String t=sc.nextLine();
char a[]=s.toCharArray();
char x[]=t.toCharArray();
int v[]= {0,0,0,0,0,0,0,0,0,0};//初始化一个数组用来存储每次相等后的下标值
int l=0;
    if(t.length()==1) {//如果用来比较的字符串长度为一那么直接比较
    if(s.contains(t)) {
    System.out.println("Yes");
    return;}
    else{
      System.out.println("No");
      return;
      }
    }
for(int i=0;i<x.length;i++) {
  char ch=x[i];
  //p1=i;

  for(int j=0;j<a.length;j++) {
   if(ch==a[j]) {
    v[l++]=j;
    a[j]='1';//把这个值设为1//因为每次都从头开始检查所以每次遇到相等的要用别的字符替换掉避免重复相等
    count++;
    break;//跳出当前循环
   }

  }
}
if(count==x.length) {
  for(int i=0;i<count-1;i++) {
   if(v[i]>v[i+1]) {//如果前面的值大于后面的值说明不是子串
    System.out.println("No");
    return;
   }if(i==count-2) {
    System.out.println("Yes");}
  }
}
else {
  System.out.println("No"+count);
}
}
}

发表于 2018-09-19 09:16:04 回复(0)

Java

🚶201804281411308

public class Program5 { public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);  String a=scanner.next();  String b=scanner.next();  if (b.equals("")) System.out.println("Yes");  else { boolean is=false;  char[] chars = b.toCharArray();  int i=a.indexOf(chars[0],0);  if (chars.length==1&&i!=-1) is=true;  for (int m=1;m<chars.length;m++){ if (a.indexOf(chars[m],i+1)!=-1){
                    is=true;  i=a.indexOf(chars[m],i+1);  } else  {
                    is=false;  break;  }
            } if (is) System.out.println("Yes");  else System.out.println("No");  }
    }
}

编辑于 2018-09-12 21:18:24 回复(0)

Java

弗兰百式

import java.util.Scanner;  /**  * Created by Leapjohn on 2018/7/22.  * t是不是s的子序列  */  public class treasure { public static void main(String[] args) {
        Scanner in =new Scanner(System.in);  String s=in.next();  char[] t=in.next().toCharArray();  int tlen =t.length;  //        String[] regex =new String[10];  StringBuffer regex =new StringBuffer();  regex.append(".");  regex.append("*");  for (int i = 0; i <t.length ; i++) {
        regex.append(t[i]);  regex.append(".");  regex.append("*");   } String tregex =regex.toString(); //        System.out.println(tregex);  if (s.matches(tregex))
        System.out.println("Yes");  else System.out.println("No");   }
}

发表于 2018-07-22 14:38:07 回复(0)

Java

爱吃青菜皮卷面的byr

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String t = sc.nextLine();
            int index = 0;
            for (int i =0 ; i<s.length();i++){
                if (t.charAt(index)==s.charAt(i)){
                    index++;
                    if (index==t.length()){
                        System.out.println("Yes");
                        return;
                    }
                }
            }
            System.out.println("No");
            return;
        }

    }
}

发表于 2018-06-04 17:19:02 回复(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)

Java

傲娇小王子

http://www.cnblogs.com/52circle/p/9019407.html
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       String m=scanner.next();
       String n=scanner.next();
       for (int i = 0; i < n.length(); i++) {
           if(m.indexOf(n.charAt(i))==-1) {
               System.out.println("No");
                return;
           }else {
           m=m.substring(m.indexOf(n.charAt(i))+1);
           }
       }
       System.out.println("Yes");
   }
}

发表于 2018-05-11 17:08:58 回复(0)

Java

杨！一叶知秋

import java.util.Scanner;

public class Main {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         while (scanner.hasNextLine()) {             String str1 = scanner.nextLine();             String str2 = scanner.nextLine();             String result = "Yes";             int length1;             int length2 = str2.length();             for (int i = 0; i < length2; i++) {                 length1 = str1.length();                 int temp = str1.indexOf(str2.charAt(i));                 if (temp == -1) {                     result = "No";                     break;                 } else {                     str1 = str1.substring(temp + 1, length1);                     continue;                 }             }             System.out.println(result);         }     }
}

编辑于 2018-04-08 15:11:50 回复(1)

Java

Mr.杜

系统提示

但是这段代码我用eclipse测试它给的测试用例，获得的结果就是No，很奇怪为什么到这里就成了Yes了

希望朋友们可以帮我找找原因（本人初学者，可能有一些简单的问题出现但是没有发觉，望指教）


	public class Main
{
 public static void main(String[] args)
 {
  String parStr = "";
  String subStr = "";
  getSubStr(parStr,subStr);
 }



	 private static void getSubStr(String parStr, String subStr)
 {
  int index = 0;
  char[] pch = parStr.toCharArray();
  char[] sch = subStr.toCharArray();
  if(sch.length==0)
  {
   System.out.println("Yes");
   return;
  }
  for(int i=0; i<sch.length; i++)
  {
   for(int j=index; j<pch.length; j++)
   {
    if(sch[i]==pch[j])
    {
     if(i == sch.length-1)
     {
      System.out.println("Yes");
      return;
     }
     index = j+1;
     break;
    }
   }
  }
  System.out.println("No");
 }
}

编辑于 2018-04-06 18:58:07 回复(0)

Java

SFISH

/*
 * 这不是很明显的用栈实现吗.............
 */

import java.util.Scanner;
import java.util.Stack;

public class Main {

public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  while(sc.hasNext()) {
   String str1=sc.nextLine();
   String str2=sc.nextLine();
   Stack<Character> stack=new Stack<>();
   for(int i=str2.length()-1;i>=0;i--)
    stack.push(str2.charAt(i));

   for(int i=0;i<str1.length();i++) {
    if(str1.charAt(i)==stack.peek()) {
     stack.pop();
    }
    if(stack.isEmpty()) {
     System.out.println("Yes");
     return;
    }
   }
   System.out.println("No");
  }

}

}

发表于 2018-04-03 09:39:36 回复(0)

Java

七仔0312

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        if (isSub(s1,s2)){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static boolean isSub(String s1, String s2) {
        if (s2 == null || "".equals(s2.trim()))
            return true;
        if (s1.contains(s2.substring(0,1))) {
            return isSub(s1.substring(s1.indexOf(s2.charAt(0))+1), s2.substring(1));
        }
        return false;
    }
}

发表于 2018-03-14 21:48:49 回复(0)

Java

shooting-zhen

import java.util.Scanner;

public class Main {
   public String isContain(String son, String father) {
       StringBuilder myString=new StringBuilder("");
       for (int i = 0; i < son.length(); i++) {
           for (int j = 0; j < father.length(); j++) {
               if (son.charAt(i)==father.charAt(j)) {
                   myString.append(son.charAt(i));
                   father = father.substring(j + 1);
                   break;
               }
           }
       }
       if(myString.length()==son.length()){
           return "Yes";
       }else{
           return "No";
       }
   }
   public static void main(String[] args) {
       Scanner sc =new Scanner(System.in);
       String father=sc.next();
       String son=sc.next();
       Main main=new Main();
       System.out.println(main.isContain(son, father));
   }
}

发表于 2018-03-10 03:05:44 回复(0)

Java

牛客1769757号

import java.util.*;
public class Main{
public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            StringBuffer father=new StringBuffer(scan.nextLine());
            StringBuffer son=new StringBuffer(scan.nextLine());
            System.out.println(getResult(father,son));
        }
        scan.close();
    }
    
    public static String getResult(StringBuffer father, StringBuffer son) {
        int length = son.length();
        int count = 0;
        //一个循环即可，将父序列循环一遍循序判断子序列中是否有某个元素，
//然后子序列索引值+1直到，父序列比较完成即可
        for(int l = 0,soni=0;l<father.length();l++) {
            if(soni<length && son.charAt(soni)==father.charAt(l)) {
                count++;
                soni++;
            }
        }
        if(count == length) {
            return "Yes";
        }
        
        return "No";
    }
}

发表于 2018-01-03 18:19:34 回复(0)

Java

傻傻傻傻

//正则匹配,字符串题目的利器
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            if (isSubSeq(str1, str2)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
    private static boolean isSubSeq(String str1, String str2) {
        if (str2 == null || str2.length() < 1) return true;
        if (str2.length() > str1.length()) return false;
        StringBuilder sb = new StringBuilder();
        sb.append(".*");
        for (int i = 0; i < str2.length(); i++) {
            sb.append(str2.charAt(i));
            sb.append(".*");
        }
        return str1.matches(sb.toString());
    }
}
----------------------------------------------------------------------
//直接比较，最高效
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            int c1 = 0, c2 = 0;
            while (c2 < str2.length()) {
                if (c1 >= str1.length()) break;
                if (str1.charAt(c1++) == str2.charAt(c2))
                    c2++;
            }
            if (c2 == str2.length()) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

编辑于 2017-12-09 14:34:42 回复(0)

Java

初生小牛不怕虎

import java.util.Scanner;   public class Main
{  public static void main(String args[]) 
    {
        Scanner scanner = new Scanner(System.in);  while (scanner.hasNext()) 
        {
            String string1 = scanner.nextLine();   String string2 = scanner.nextLine();  int j = find(0, string2.charAt(0), string1);  int i;  if (j == -1) 
            {
                System.out.println("No");  }  else  {  for (i = 1; i < string2.length(); i++) 
                {
                    j = find(j + 1, string2.charAt(i), string1);  if (j == -1) 
                    {
                        System.out.println("No");  break;   }
                }  if (i == string2.length()) 
                {
                    System.out.println("Yes");   }
            }
        }
    }  private static int find(int i, char a, String string) 
    {  int length = string.length();  for (int j = i; j < length; j++) 
        {  if (string.charAt(j) == a) 
             { return j;  }
        }   return -1;   }
}


这道题我觉得循环查找，对每个string2中的字符在string1中进行查找，重要的是需要控制顺序，所以

这就需要我们控制查找的开始位置和当前要查找的字符，所以把它独立出来做成一个查找函数，我觉得是

比较关键的问题，另外还要考虑到各种可能的情况，比如我就没有考虑到如果二者都是只有一个字符的

字符串的情况，后面有加上了那个判断条件才通过所有用例。