LeetCode "Is Subsequence"

There are 3 possible approaches: DP, divide&conquer and greedy. And apparently, DP has O(n^2) complexity (TLE), DivideConquer can only be worse. Greedy can be O(n)! And its code is amazingly brief:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        size_t lens = s.length();
        size_t lent = t.length();

        int is = 0, it = 0;
        while(is < lens && it < lent)
        {
            char cs = s[is], ct = t[it];
            if(cs != ct) it ++;
            else is++, it++;
        }
        
        return is == lens;
    }
};
原文地址:https://www.cnblogs.com/tonix/p/5991652.html