Is Subsequence https://leetcode.com/problems/is-subsequence/
- DP is an overkill for this problem. Also DP should not use N^2 space. Check the code.
- Two pointer solution - Maintain i and j equal to 0.Fix i and move j until we have s[i]==t[j]. The success condition is when i has reached end of string.
class Solution(object): def isSubsequence(self, s, t): """ :type s: str :type t: str :rtype: bool """ i,j = 0,0 while j < len(t) and i < len(s): if s[i] == t[j]: i += 1 j += 1 return i == len(s)