There are 3 possible approaches: DP, divide&conquer and greedy. And apparently, DP has O(n^2) complexity, 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; } };
原文：http://www.cnblogs.com/tonix/p/5991652.html