Friday, May 3, 2024 8:07 EDT

Leetcode 392. Is Subsequence (Easy)

Beats 100% of users using C++ on time.
Beats 69.03% of users using C++ on space.

Approach
This problem is to determine if input s is a subsequence of t.

Fortunately, the instructions state that the subsequence is in-order meaning "ace" is a subsequence of "abcde" but "aec" is not.

At minimum I know there is going to be some kind of loop involved. I will start by determining which input string to loop over. According to the constraints it would seemingly make sense to iterate over s due to it's size (see below), however, our search space is t so we will need to start there.

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist only of lowercase English letters.

The next step is to declare another pointer j as this will keep track of what character I am searching for in t. I will initialize this to 0 to start.

Inside the loop, I want to to do two things:

• Check if the current character in t matches the current character in s
• Check if the index j is the length of s

If the first is true, then a match was found and I can move on to the next character in s.

If the second is true, then I have found the subsequenece and can return true.

If the loop completes and j never equaled s.length() then s is not a subsequence of t and return false.

The last part, which is a lazy way to handle empty strings, is first line of the function. Any empty string s will always be a subsequence of any t. Checking for empty() is the same as length() == 0 which both run in constant time so there is little time loss on this operation.

Complexity
Time Complexity: O(n)
Space Complexity: O(1)

Code

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.empty()) return true;
        int j = 0;
        for(int i = 0; i < t.length(); i++){
            if(t[i] == s[j]){
                j++;
            }
            if(j == s.length()){
                return true;
            }
        }
        return false;
    }
};