Using Two Pointers for Different Arrays is Simple

Today’s problem was asked by Google. The problem name is Is Subsequence?

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

The simplest idea to solve this problem is by iterating each items of s and t while maintaining its pointer. Let’s say you have i for pointer the s and j for pointer the t. While iterating each elements, you do the check, if the item of s[i] and t[j] is equal, if yes, you increment the i += 1 then you increment j += 1, if not the loop will run endlessly.

It’s worth to mention that you can add checks to return early if the i is equal to the length of s . With this way you add an early exit to the code and prevent unnecessary iterations.

Hence, the code would be:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        S = len(s)
        T = len(t)
        if S == 0: return True
        if T < S: return False
        i, j = 0, 0

        while j < T:
            if s[i] == t[j]:
                i += 1
                if i == S:
                    return True
            j += 1
            
        return i == S

With this approach, I achieve the runtime of 0ms also beat 100% solution out there.

Alright, I think that’s enough for today’s practice. You can revisit the previous post and try to re-solve the problem without looking at the answer to ensure you fully understand the idea/concept behind the code.

If you have any questions related to this post or tech, comment down below.