Is Subsequence

这道题初看肯定觉得是DP，当然DP是可以做这道题，但是因为只是判断子序列这种要求，实际上可以用一个类似one edit distance的贪心算法去做，这也算很少的能比较直接的想到贪心的题目了，先把DP算法写下，LC会MLE

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        n, m = len(s), len(t)
        dp = [[False] * (m + 1) for _ in xrange(n + 1)]

        for i in xrange(m + 1):
            dp[0][i] = True

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = dp[i][j - 1]

        return dp[n][m]

再因为我们要找的是子序列，那就可以双指针，两个字符相等全往前移，不相等只移t指针，这样最后的结果肯定就是看s指针是不是移到终点了

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        n, m = len(s), len(t)
        startS, startT = 0, 0
        while startS < n and startT < m:
            if s[startS] == t[startT]:
                startS += 1
                startT += 1
            else:
                startT += 1

        return startS >= n

此题还可以用二分做，具体等三刷再研究吧