Is Subsequence

LeetCode Q 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 is about 500,000) string, and s is a short string (<=100).
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?

Solution

1. Solution 1

Code:

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

public boolean isSubsequence(String s, String t) {
	if (s.length() == 0) return true;
	if (s.length() > t.length()) return false;
	for (int i = 0; i < s.length; i++) {
		int index = t.indexOf(s.charAt(i));
		if (index == -1) return false;
		t = t.substring(index + 1);
	}
	return true;
}

2. Solution of Follow Up Question

If we check each s in this way, then it would be O(kn) time where k is the number of s and n is the length of t. This is inefficient.  Since there is a lot of s, it would be reasonable to preprocess t to generate something that is easy to search for if a character of s is in t. Sounds like a HashMap, which is super suitable for search for existing stuff.

1. Build a map, key is the char in String t, value is a list contianing the index of the char in t.

2. Use binary search to find if each char in String s exists in t.

Code:

public boolean isSubsequence(String s, String t) {
	Map<Character, List<Integer>> map = new HashMap<>();
	for (int i = 0; i < t.length(); i++) {
		map.putIfAbsent(t.charAt(i), new ArrayList<>());
		map.get(t.charAt(i)).add(i);
	}
	int prev = -1;
	for (char ch: s.toCharArray()) {
		prev = binarySearch(map, ch, prev);
		if (prev == -1) return false;
		prev++;
	}
}

private int binarySearch(Map<Character, List<Integer>> map, char ch, int index) {
	if (!map.containsKey(ch)) return -1;
	List<Integer> list = map.get(ch);
	int lo = 0, hi = list.size() - 1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		if (list.get(mid) < index)
			lo = mid + 1;
		else 
			hi = mid - 1;
	}
	return lo == list.size() ? -1 : list.get(lo);
}