题解 | #判断子序列#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    // 双指针
    bool isSubsequence(string S, string T) {
        // write code here
        int i=0, j=0;
        for(; j<T.length(); j++){
            if(i < S.length() && S[i] == T[j]){
                i++;
            }
        }
        return i == S.length();
    }
    
    // 转化为最长公共子序列问题
    /*
    bool isSubsequence(string S, string T) {
        // write code here
        int m=S.length(), n=T.length();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(S[i-1] == T[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j], 
                                   max(dp[i][j-1], dp[i-1][j-1]));
                }
            }
        }
        return dp[m][n] == S.length();
    }
    */
    
};