Python solution with detailed explanation


  • 0
    G

    Solution

    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)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.