Description
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).
Examples:
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: falseSolution in Python
Approach:
- Use two pointers, one for
s(let’s call iti) and one fort(let’s call itj). - Start from the beginning of both strings.
- Move the pointer
jthrought, checking each character:- If
t[j]matchess[i], moveito the next character ins. - If
t[j]does not matchs[i], just movej.
- If
- If we reach the end of
s(i == len(s)), it means all characters inswere found intin the correct order, sosis a subsequence oft. - If we reach the end of
tbefore finishings,sis not a subsequence oft.
Python
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# Pointers for s and t
i, j = 0, 0
# Traverse through t until we find all characters of s or reach the end of t
while i < len(s) and j < len(t):
# If characters match, move the pointer in s
if s[i] == t[j]:
i += 1
# Always move the pointer in t
j += 1
# If i has reached the end of s, it means all characters were found in sequence
return i == len(s)Explanation with Example:
- Example 1:
s = "abc",t = "ahbgdc"- Compare each character of
swithtusing pointers. - Matches found in order for “a”, “b”, and “c” in
t. ireaches the end ofs, sosis a subsequence oft→ returnTrue.
- Compare each character of
- Example 2:
s = "axc",t = "ahbgdc"- Compare each character of
switht. - “a” matches, but “x” does not have a corresponding position in
t. idoes not reach the end ofs→ returnFalse.
- Compare each character of
Solution in C++
C++
class Solution {
public:
bool isSubsequence(string s, string t) {
// Initialize two pointers, one for each string
int sIndex = 0; // Pointer for string s
int tIndex = 0; // Pointer for string t
// Traverse through string t
while (tIndex < t.length() && sIndex < s.length()) {
// If characters at both pointers match, move the pointer for s
if (s[sIndex] == t[tIndex]) {
sIndex++; // Move to the next character in s
}
// Always move the pointer for t
tIndex++; // Move to the next character in t
}
// If we've matched all characters in s, sIndex should be equal to s.length()
return sIndex == s.length();
}
};Solution in Javascript
JavaScript
var isSubsequence = function(s, t) {
// Initialize pointers for both strings s and t
let sPointer = 0; // Pointer for string s
let tPointer = 0; // Pointer for string t
// Loop through both strings until we reach the end of either string
while (sPointer < s.length && tPointer < t.length) {
// If characters at both pointers match, move the pointer of s forward
if (s[sPointer] === t[tPointer]) {
sPointer++;
}
// Always move the pointer of t forward to continue checking the next character
tPointer++;
}
// If sPointer has reached the end of s, then all characters in s
// were found in t in the correct order, so s is a subsequence of t
return sPointer === s.length;
};Solution in Java
Java
class Solution {
public boolean isSubsequence(String s, String t) {
// Initialize two pointers, one for each string.
int sPointer = 0; // Pointer for string s
int tPointer = 0; // Pointer for string t
// Loop until we reach the end of either s or t
while (sPointer < s.length() && tPointer < t.length()) {
// Check if the current characters of s and t are equal
if (s.charAt(sPointer) == t.charAt(tPointer)) {
// If they match, move the pointer in s to check the next character
sPointer++;
}
// Always move the pointer in t to the next character
tPointer++;
}
// If sPointer has reached the end of s, it means all characters in s
// were found in t in the correct order, so s is a subsequence of t.
// Otherwise, s is not a subsequence of t.
return sPointer == s.length();
}
}