[Top Interview 150] 392. Is Subsequence

Solution)

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        original, sub = 0, 0

        while sub < len(s) and original < len(t):
            if s[sub] == t[original]:
                sub += 1
            
            original += 1
        
        if sub == len(s):
            return True
        return False

 

Problem: LeetCode

 

Time Complexity: O(m+n)

Space Complexity: O(1)

Explanation)

There are two pointers sub and original that will iterate s and t.

We're using two pointers because we have to check each character from each variable in different steps. By different steps I mean whenever original increases by one every loop, sub might not.

 

While iterating t (meaning original will be increased by one every loop), if the same character is found in s, we'll increase sub by one.

 

After the iteration is complete, we'll check if sub equals to the len(s), which means every character in s was found in t.

Thus, s is a subsequence of t and we'll return True.

Initialization)

Since we are using two pointers that will iterate two variables, let's initialize those pointers to zero.

 

def isSubsequence(self, s: str, t: str) -> bool:
        original, sub = 0, 0

While loop)

When using two pointers and need to set up a loop, I usually use a while loop with a condiiton regarding the pointers and the length of a variable.

 

This allows us not only to iterate through an item completely and separately, but also to prevent us from encountering index error or out-of-bound error.

 

Because we want to completely iterate either s or t, we'll set up the condition as below. 

 

Then whenever we find a common character, sub will increase by one so that we can check if there are other common characters. original will be increased every loop.

 

def isSubsequence(self, s: str, t: str) -> bool:
        original, sub = 0, 0

        while sub < len(s) and original < len(t):
            if s[sub] == t[original]:
                sub += 1
            
            original += 1

Is Subsequence?)

If one of the string variables' iteration is completed, we'll check if sub equals to the length of s.

 

If sub equals to the length of s, that means the while loop above was completed as the condiiton "sub < len(s)" is broken. The condition "sub < len(s)" is broken because sub was increased as the same character was found in t during the iteration. 

 

If sub was increased up until the length of sub was reached, that means every character of s was found in t. Thus, s is a subsequence of t. We can return True.

 

If that's not the case we'll return False.

 

def isSubsequence(self, s: str, t: str) -> bool:
        original, sub = 0, 0

        while sub < len(s) and original < len(t):
            if s[sub] == t[original]:
                sub += 1
            
            original += 1
        
        if sub == len(s):
            return True
        return False

 

 

I've solved 50 LeetCode prolbems so far. I remember not being able to solve a single problem by myself for the first 10 or 15 problems. It's amazing how I can design the structure of the codes now and I love how I'm seeing progress. Can't wait to see myself done with Top Interview 150.

 

Thank you for visiting my blog and please let me know if you have any quesitons :)