Python solution with detailed explanation

  • 0


    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.