题解 | #判断子序列#

判断字符串的子序列问题，一种做法是基于动态规划计算公共子序列，若公共子序列等于字符串S则说明S是T的子序列。这样做的解法时间复杂度是O(n²），但实际上不用这么麻烦，存在更简单容易理解的时间复杂度为O(N)的方法：

【C++ 代码】

class Solution {
public:
    /**
     * 
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    bool isSubsequence(string S, string T) {
        // 1. 记录字符串S和T的长度
        int m = S.length();
        int n = T.length();
        // 2. 声明变量p指示对字符串S的当前遍历位置
        int p = 0;
        // 3. 从左到右遍历字符串T
        for(int i=0; i<n; ++i){
            // 4. 如果当前字符等于指针p指示的字符，则下一个目标是在字符串T中寻找与S[p+1]相等的字符
            if(T[i] == S[p]){
                ++p;
            }
        }
        // 5. 最后如果遍历完S字符串则说明S是T的子序列
        return  p==m;
    }
};