Dare2Solve
To determine if a string s
is a subsequence of another string t
, we need to check if all characters of s
appear in t
in the same order. This means we can "skip" characters in t
but must match all characters in s
sequentially. By iterating through both strings simultaneously and ensuring that each character in s
finds a matching character in t
in the correct order, we can verify if s
is a subsequence of t
.
Initialize Indices:
Start with two indices, one for each string (sIndex
for s
and tIndex
for t
), both set to 0.
Iterate Through Strings:
Use a while loop to iterate through both strings:
s
(s[sIndex]
) matches the current character of t
(t[tIndex]
), increment sIndex
.tIndex
to continue checking the next character in t
.Check Completion: After the loop, if sIndex
has reached the length of s
, it means all characters in s
were found in t
in the correct order, so return true
. Otherwise, return false
.
O(n), where n
is the length of the string t
. In the worst case, we may have to traverse the entire string t
to determine if s
is a subsequence.
O(1), as we only use a constant amount of extra space for the indices.
class Solution {
public:
bool isSubsequence(string s, string t) {
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s[sIndex] == t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex == s.length();
}};
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s_index, t_index = 0, 0
while s_index < len(s) and t_index < len(t):
if s[s_index] == t[t_index]:
s_index += 1
t_index += 1
return s_index == len(s)
class Solution {
public boolean isSubsequence(String s, String t) {
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s.charAt(sIndex) == t.charAt(tIndex)) {
sIndex++;}
tIndex++;}
return sIndex == s.length();
}}
var isSubsequence = function (s, t) {
let sIndex = 0, tIndex = 0;
while (sIndex < s.length && tIndex < t.length) {
if (s[sIndex] === t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex === s.length;
};