题解 | #判断子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    public boolean isSubsequence (String s, String t) {
        // write code here
        
        if(s.length() == t.length()) {
            if(s.equals(t)){
                System.out.print(true);
                return true;
            } else {
                System.out.print(false);
                return false;
            }
        }
        
        if(s.length() > t.length()) {
            System.out.print(false);
            return false;
        }
	  	//字符串t的前i个字符中匹配个数
        int[] dp = new  int[t.length()+1];
        for(int i=0; i<t.length()+1; i++) {
            dp[i] = 0;
        }
        int cur = 1;// 2 10 now1","nowcoder1"
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(cur <= t.length()) {
                for(  ;cur<t.length()+1; cur++) {
                    if(c == t.charAt(cur-1)) {
                        dp[cur] = dp[cur-1] + 1;
                        cur++;
                        break;
                    } else {
					  //不匹配，往后移，当前匹配数等于上个匹配数
                        dp[cur] = dp[cur-1];
                    }
                }
            }
            if(cur > t.length()) {
                break;
            }
        }
        if(dp[t.length()] == s.length()) {
            System.out.print(true);
            return true;
        }
        System.out.print(false);
        return false;
    }
}