Created
August 7, 2023 05:11
-
-
Save ritik-agrawal/0a7bf0864fea2beb69adfaf3dade9633 to your computer and use it in GitHub Desktop.
LeetCode: isSubsequence, given with two strings return true if `s` is subsequence of `t` .
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public boolean isSubsequence(String s, String t) { | |
var slen = s.length(); | |
var tlen = t.length(); | |
if (slen == 0){ | |
return true; | |
} | |
if (tlen < slen){ | |
return false; | |
} | |
var sc = 0; | |
for (int i = 0; i < tlen; i++){ | |
if (sc < slen && s.charAt(sc) == t.charAt(i)){ | |
sc++; | |
} | |
} | |
return (sc == slen); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Example
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 ofabcde
whileaec
is not).Observation
The above problem has been solved using an algorithm with two different implementations.
Algorithm
s
length is equal to zero then returntrue
.t
length is less than thes
length then returnfalse
.s
character after it's seen in 't's
length then returntrue
elsefalse
.Implementation 1
Using the
s.toCharArray()
. This implementation beats 54% of the total solutions submitted with a runtime of 2 ms.Implementation 2
Using
s.charAt(i)
to iterate through the strings given instead of the array index. This implementation beats 89% of total solutions submitted with a runtime of 1 ms.Click here for the Leetcode submission page.