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

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?

解法1： Two pointers O(M + N)

一个指针扫描t，一个指针扫描s。当两个指向的字符相同的时候就把s的指针前进，如果s到了t的末尾，那么就返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (t == null || t.length() == 0) {
            return false;
        }
        int j = 0;
        for (int i = 0; i < t.length(); i++){
            if (t.charAt(i) == s.charAt(j)) {
                j++;
                if (j == s.length()) {
                    return true;
                }
            }
        }
        return false;
    }
}

Follow up

如果是要不停的处理不同的s的话，一般情况下可以对t进行一些预处理。
首先用O(N)的办法得出每一个字符在t中出现的位置，用一个Map>处理。
然后遍历每一个s中的字符，同时维护一个prev记录上一次在s中match到的位置。
如果一个字符不存在map中，直接返回false
如果一个字符在map中，取得该character在t中的位置的list。
然后可以用一个binarysearch取得最小的比prev大的数字。
如果这个数字不存在，那么就返回false。
如果存在则match这个，同时把prev设为该index的下一个。
复杂度可以降低到O(MlogN)

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
class Solution {
    public boolean isSubsequence(String s, String t) {
        if ( s == null || s.length() == 0) {
            return true;
        }
        // preprocess, O(N)
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, new ArrayList<>());
            }
            map.get(ch).add(i);
        }
        int prev = 0;
        for (char ch : s.toCharArray()) {
            if (!map.containsKey(ch)) {
                return false;
            }
            List<Integer> pos = map.get(ch);
            int index = Collections.binarySearch(pos, prev);
            if (index < 0) index = (-1)*(index + 1);
            if (index == pos.size()) return false;
            prev = pos.get(index) + 1;  // index stores the insertion position, so to get the real position in t you have to get from the list
        }
        return true;
    }
}