392. Is Subsequence - June day 9
link to leetcode problem definition
Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
This problem comes down to a recursive solution with a greedy idea behind. We need to compare all characters of S with characters of T and if there is a match cross that as a result for the occurrence of the first character and move on. Our base case would be when all characters of S have been matched up and no more left, essentially when S is empty.
- S has no characters -> return true
- T has no characters (but S has) -> return false, meaning we exhausted T but still have some characters in S to match up
- Iterate over T and compare characters of T to first of S
class Solution {
public boolean isSubsequence(String s, String t) {
var sLen = s.length();
var tLen = t.length();
if(sLen == 0) {
return true;
}
for(int i = 0; i < tLen; i++) {
if(s.charAt(0) == t.charAt(i)) {
return isSubsequence(s.substring(1, sLen), t.substring(i + 1, tLen));
}
}
return false;
}
}