Leetcode Problem #392: Is Subsequence. An Efficient Two-Sum Solution Using Hash Table

Photo by Vedrana Filipović on Unsplash

Let’s move on with another Leetcode problem. This one is a great way to practice Lists for beginners. Again, we’ll apply the process suggested in Cracking the Coding Interview by Gayle Laakmann McDowell.

TLDR;

Just loop the T List and use an index for s. Check each character in T and compare them to s.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        """
        Time: O(N)
        Space: O(1)
        """
        s_idx = 0
        s_len = len(s)
        t_len = len(t)

        # Special Cases
        if  s_len == 0: 
            return True

        if t_len == 0 and s_len > 0: 
            return False

        # Loop
        for char in t: 
            if char == s[s_idx]:
                s_idx += 1
                if s_idx == s_len:
                    return True
        return False

1. Listen
2. Example
3. Brute Force
4. Optimize
5. Walkthrough
6. Implement
7. Test

So let’s begin:

First, we start by reading the problem:

Given two strings s and t, return true if…