Leetcode 75: Day 2: 392. Is Subsequence
Question:
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).
Example 1:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 100 0 <= t.length <= 104 s and t consist only of lowercase English letters.
Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?
Solution:
- Keep a pointer j that will point at the characters in s string.
- If length of s string is greater than t, return false as subsequence is not possible.
- Iterate over the characters in t string.
- If any character at ith position matches the character at jth position in s string, increment j, provided j is smaller than length of s.
- At the end, if j is not equal to the length of the s string, return false, else return true.
Code:
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length() > t.length()) return false;
int j = 0;
for(int i = 0; i < t.length(); i++){
if(j < s.length() && t.charAt(i) == s.charAt(j)){
j++;
}
}
if(j != s.length()) return false;
return true;
}
}
Complexity:
- Time: O(N)
- Space: O(1)