392. Is Subsequence
Description of Problem
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 <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 10^9, 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 1
Tags: Two Pointers
Explanation
Use two distinct pointers to scan oven string s and t. When they have the same character, move both pointers. Otherwise, move t's pointer only.
If the scanning of s is not completed, then s is not the subsequence of t.
Code (Rust)
impl Solution {
pub fn is_subsequence(s: String, t: String) -> bool {
let (s,t) = (s.as_bytes(), t.as_bytes() );
let (mut i, mut j) = (0,0);
while i < s.len() && j < t.len(){
if s[i] == t[j]{
i+=1;
}
j+=1;
}
return i == s.len();
}
}
Complexity
- m is length of
t - n is length of
s
Time Complexity
- \( T(n) = O(\min(m,n)) \)
Auxiliary Space
- \( S(n) = O(1) \)
Solution 2 - Follow-up
Tags: HashSet/HashMap
Explanation
Intutively, find the list of indices \( I \) such that \( s = t[i_0] + t[i_1] + ... + t[i_{n-1}]\)
Example
s = "abc"
t = "axxxxbbxxxbbbxxxxcc"
s = t[0] + t[5] + t[17]
= t[0] + t[6] + t[17]
= ...
= t[0] + [12] + t[18]
Code (Rust)
impl Solution {
pub fn is_subsequence(s: String, t: String) -> bool {
use std::collections::HashMap;
let mut map : HashMap<char, Vec<usize>>= HashMap::new();
// Build (character, Vec<index>) map
for (i,ch) in t.chars().enumerate(){
map.entry(ch).and_modify(|v| v.push(i)).or_insert(vec![i]);
}
let mut curr_idx = None;
for (i, ch) in s.chars().enumerate() {
// characters `ch` is in `t`
if let Some(v) = map.get(&ch) {
// Extract idx from `curr_idx` if exists
if let Some(idx) = curr_idx {
// Find the minimum index in `t` which is greater then `idx`
let next_idx = v.iter().filter( |&x| idx < x ).min();
// No character `ch` is found in `t` after `t[idx]`
if next_idx.is_none(){
return false
}
// Update `curr_idx`
else{
curr_idx = next_idx;
}
}
// the `curr_idx` is None. i.e. This is the first character we read
else{
curr_idx = Some(&v[0]);
}
}
// No such characters in `t`
else{
return false;
}
}
return true;
}
}
Complexity
- m is length of
t - k is the number of incoming requests
- n is maximum length of strings amongst
si
Time Complexity
- \( T(n) = O( m + n \cdot k ) \)
Auxiliary Space
- \( S(n) = O(m) \)
- The HashMap equivalently stores entries in HashMap.