你的位置:首页 > Java教程

[Java教程]牛客网算法题之All


题目:

有两个字符串s 和t,如果即从s 中删除一些字符,将剩余的字符连接起来,即可获得t。则称t是s 的子序列。
请你开发一个程序,判断t是否是s的子序列。

输入描述:

输入包含多组数据,每组数据包含两个字符串s和t。

它们都由数字和字母组成,且长度小于100000。

输出描述:

对应每一组输入,如果t是s的子序列,则输出“Yes”;否则输出“No”。

输入例子:

ABC ABC
ABC AB
ABC DE

输出例子:

Yes
Yes
No

代码:
package niuke;import java.util.Scanner;public class Main {  public static void main(String[] args) {    Scanner read = new Scanner(System.in);    while(read.hasNext())    {      String str1 = read.next();      String str2 = read.next();      judgeStr(str1, str2);    }    read.close();  }  /**   *   * @param source   * @param target   * @return   */  public static int indexOf(char[] source, char[] target) {        int targetCount = target.length;    int sourceCount = source.length;        if (targetCount == 0) {      return 0;    }    char first = target[0];    int max = sourceCount - targetCount;    for (int i = 0; i <= max; i++) {      if (source[i] != first) {        while (++i <= max && source[i] != first)          ;      }      if (i <= max) {        int j = i + 1;        int end = j + targetCount - 1;        for (int k = 1; j < end            && source[j] == target[k]; j++, k++)          ;        if (j == end) {          return i;        }      }    }    return -1;  }    public static void judgeStr(String str1, String str2)  {    int len1 = str1.length(), len2 = str2.length();        int i = 0, j = 0;        for(; i<len1 && j<len2;)    {      if(str1.charAt(i) == str2.charAt(j))      {        j ++;      }      i ++;    }        if(j == len2)    {      System.out.println("Yes");    }    else    {      System.out.println("No");    }  }}

注解:

题目本身不难,重点是对题目的理解。

代码中indexOf(String, String)方法为此题的一个错误理解,即理解成必须全部包含才能输出Yes,

如“ABCD" "AB"  输出 “Yes"

对于“ABCD" "AD" 输出”No"

但是题目本身的意思是对于“ABCD" "AD" 也要输出”Yes“