392. Is Subsequence Easy
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
Approach
Input: Two strings s and t
Output: Determine if s is a subsequence of t
This is a same-direction two pointers problem.
We can use two pointers starting simultaneously from the left sides of the two strings.
When the characters pointed to by the left and right pointers match, the left pointer (pointing to s) moves to the right.
Whether it matches or not, the right pointer (pointing to t) always moves to the right.
Finally, we just need to check if the left pointer has traversed the entirety of string s.
Implementation
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# Special case handling: if s is longer than t, it cannot be a subsequence
if len(s) > len(t):
return False
# Two-pointer method
i, j = 0, 0 # i points to s, j points to t
# Iterate through t, matching characters in s
while i < len(s) and j < len(t):
if s[i] == t[j]:
# A character is matched, move i forward
i += 1
# Regardless of whether the match is successful, j must move forward
j += 1
# If i fully iterated through s, it means all characters were successively matched
return i == len(s)/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
let l = 0;
let r = 0;
while (l < s.length && r < t.length) {
if (s[l] == t[r]) {
l ++;
}
r++;
}
return l === s.length;
};Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)