[LeetCode] 392. Is Subsequence

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 sis 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).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

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?

Thought process:

Greedy. Iterate through both s and t. As soon as I see t[j] == s[i], increment s[i]. If s[i] can be iterated through, then it's a sub-sequence of t.

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class Solution { public boolean isSubsequence(String s, String t) { int i = 0; int j = 0; while (j < t.length()) { if (i == s.length()) { return true; } if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == s.length(); } }

Time complexity:
Say the length of t is n. Then the overall time complexity is O(n).

Follow up:
Our current solution is O(n), where n is the length of t. If there are lots of incoming s, out solution won't be satisfactory because n is very large.
Binary search. For each character from a - z, create a list of indices where the character occurs in t. Iterate through s. For each character in s, go to its corresponding list, and binary search for the earliest index where the character occurs in t. Use a variable "previous" to keep track of that index. If in any iteration, binary search returns an index that's out of range of the list, return false, because that means a character that appears later in s has no match in t.

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public class Solution { public boolean isSubsequence(String s, String t) { List<Integer>[] positions = new List[26]; for (int i = 0; i < t.length(); i++) { char c = t.charAt(i); int index = c - 'a'; if (positions[index] == null) { positions[index] = new ArrayList<>(); } positions[index].add(i); } int last = 0; for (char c : s.toCharArray()) { int index = c - 'a'; if (positions[index] == null) { return false; } int insertion = Collections.binarySearch(positions[index], last); if (insertion < 0) { insertion = - (insertion + 1); } if (insertion == positions[index].size()) { return false; } last = positions[index].get(insertion) + 1; } return true; } }

Time complexity:
Say length of s = a and length of t = b. The first for loop takes O(b). The second for loop takes O(alogb). The overall time complexity is O(alogb).