牛客網算法題之All-in-All，牛客all-in-all

牛客網算法題之All-in-All，牛客all-in-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“