[LeetCode] 392. Is Subsequence

1. Question

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

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

2. Thoughts

3. Tips learned

(From AI Solution)
The find() method is a built-in function in Python used with strings. It searches for a specified value and returns the position of where it was found. If the value is not found, the method returns -1.

Here's the syntax of the find() method:

str.find(sub, start, end)

• sub: The substring you want to find.
• start (optional): The start position where the method should begin searching. Default is 0.
• end (optional): The end position where the method should stop searching. Default is the end of the string.

Here's an example of how you might use the find() method:

text = "Hello, World!"
position = text.find("World")
print(position)  # Output will be 7

In the context of your problem, the find() method is used to search for the next occurrence of a character in the target string t, starting from the current index index_t. It simplifies the code by replacing the need for a manual loop to iterate through the characters of the string.

4. My solution

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        index_t = 0
        for char_s in s:
            while index_t < len(t) and char_s != t[index_t]:
                index_t += 1
            if index_t == len(t):
                return False
            index_t += 1

        return True

19/19 cases passed (33 ms)
Your runtime beats 96.65 % of python3 submissions
Your memory usage beats 90.36 % of python3 submissions (16.3 MB)

5. AI Solution and Improvements

Your code is correct and works well for determining if s is a subsequence of t. It iteratively matches each character of s with t, advancing the index in t until a match is found or the end of t is reached.

However, the code can be slightly optimized by removing the inner while loop and using Python's string methods. Here's an alternative approach:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        index_t = 0
        for char_s in s:
            index_t = t.find(char_s, index_t)
            if index_t == -1:
                return False
            index_t += 1
        return True

In this version, the find method is used to find the index of the next occurrence of char_s in t starting from the current index_t. If char_s is not found, find returns -1, and the function returns False. Otherwise, the index is incremented to search beyond the current match in the next iteration.

This version simplifies the code while preserving the correct logic.