easyStringsPattern: Two Pointers
Subsequence Matcher Solution
Problem Statement
Given two strings, determine if the first string is a subsequence of the second string.
Examples
Example 1:
Input:abc
bc
Output:true
Explanation: Since 'abc' is a subsequence of 'bc'.
Example 2:
Input:abc
bca
Output:false
Explanation: Because not all characters occur in the same order.
Example 3:
Input:abc
xyz
Output:false
Explanation: 'abc' is not a subsequence since none of its characters are found next to each other in 'xyz'.
Example 4:
Input:
Output:true
Explanation: If the first string is empty, it is a subsequence of any string.
Example 5:
Input:string
Output:true
Explanation: If both strings are identical.
Constraints
- The length of the strings can be up to 100 units.
- Strings can contain only lowercased English letters (a-z).
- Test cases will cover various possible scenarios, such as: different lengths, unique and repeating characters.
Time: O(n * m) Space: O(1)
The optimized approach uses two pointers, one for each string. One pointer moves through the first string and checks if the current character exists in the second string. If it does, we advance the pointer in the first string. If we've covered the entire second string with matching order of characters, the first string is a subsequence of the second string.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def is_subsequence(str1, str2):
p1 = p2 = 0
while p1 < len(str1) and p2 < len(str2):
if p2 < len(str2) and str1[p1] == str2[p2]: p1 += 1
p2 += 1
return p1 == len(str1)