Skip to content

Latest commit

 

History

History
145 lines (128 loc) · 4.3 KB

392. Is Subsequence.md

File metadata and controls

145 lines (128 loc) · 4.3 KB
Raw

392. Is Subsequence

leetcode-cn Daily Challenge on July 27th, 2020.

Difficulty : Easy

Related Topics : Greedy、Binary Search、Dynamic Programming

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

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?

Credits:

Special thanks to @pbrother for adding this problem and creating all test cases.

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 <= 10^4
  • Both strings consists only of lowercase characters.

Solution

  • mine

    • Java

      Runtime: 1 ms, faster than 92.60%, Memory Usage: 38.8 MB, less than 74.10% of Java online submissions

      // O(L)time  O(1)space
// L is Math.max(len(s),len(t))
public boolean isSubsequence(String s, String t) {
    int f = 0;
    int l = 0;
    while (f < s.length() && l < t.length()) {
        if (s.charAt(f) == t.charAt(l)) {
            f++;
        }
        l++;
    }
    return f == s.length();
}

      the following code will be faster. Runtime: 1 ms, faster than 92.60%, Memory Usage: 39.2 MB, less than 70.17% of Java online submissions

      // O(L)time  O(L)space
// L is Math.max(len(s),len(t))
public boolean isSubsequence(String s, String t) {
    char[] arrS = s.toCharArray();
    char[] arrT = t.toCharArray();
    int f = 0;
    int l = 0;
    while(f < s.length() && l < t.length()){
        if(arrS[f] == arrT[l]){
            f++;
        }
        l++;
    }
    return f == arrS.length;
}
  • the fastest
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.6 MB, less than 78.83% of Java online submissions 
      //O(Math.max(len(s),len(t)))time  O(len(s))space
public boolean isSubsequence(String s, String t) {
    char[] arr = s.toCharArray();
    int j = -1;
    for (int i = 0; i < arr.length; i++) {
        j = t.indexOf(arr[i], j + 1);
        if (j == -1) {
            return false;
        }
    }
    return true;
}
  • the most votes

    • Binary search solution for follow-up with detailed comments

      Runtime: 4 ms, faster than 55.57%, Memory Usage: 39.9 MB, less than 65.77% of Java online submissions

      // Follow-up: O(N) time for pre-processing, O(Mlog?) for each S.
// Eg-1. s="abc", t="bahbgdca"
// idx=[a={1,7}, b={0,3}, c={6}]
//  i=0 ('a'): prev=1
//  i=1 ('b'): prev=3
//  i=2 ('c'): prev=6 (return true)
// Eg-2. s="abc", t="bahgdcb"
// idx=[a={1}, b={0,6}, c={5}]
//  i=0 ('a'): prev=1
//  i=1 ('b'): prev=6
//  i=2 ('c'): prev=? (return false)
public boolean isSubsequence(String s, String t) {
    List<Integer>[] idx = new List[256]; // Just for clarity
    for (int i = 0; i < t.length(); i++) {
        if (idx[t.charAt(i)] == null)
            idx[t.charAt(i)] = new ArrayList<>();
        idx[t.charAt(i)].add(i);
    }
    
    int prev = 0;
    for (int i = 0; i < s.length(); i++) {
        if (idx[s.charAt(i)] == null) return false; // Note: char of S does NOT exist in T causing NPE
        int j = Collections.binarySearch(idx[s.charAt(i)], prev);
        if (j < 0) j = -j - 1;
        if (j == idx[s.charAt(i)].size()) return false;
        prev = idx[s.charAt(i)].get(j) + 1;
    }
    return true;
}