392. Is Subsequence

Q:

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?

A:

就是一个个地数，发现就行。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        int k =0; // index for t
        for(int i =0;i<s.length();i++){
            char ch = s.charAt(i);
            while(k<t.length() && t.charAt(k) != ch){
                k++;
            }
            if( k >=t.length())
                return false;
            k++;  
        }
        return true;
    }
}
 

Follow up的情况，就是把 t 预先处理，  save the position of each character
为了更speed up ， 我们搜索的时候，把当前搜索到的位置，也保存下来。

public class Solution {
    public boolean isSubsequence(String s, String t) {
        //init :  record the location for each char
        List<List<Integer>> all = new ArrayList<>();
        for(char ch = 'a'; ch<= 'z'; ch++ ){
            List<Integer> list = new ArrayList<>();
            all.add(list);
        }
        for(int i =0;i<t.length(); i++){
            char ch = t.charAt(i);
            int index = ch -'a';
            all.get(index).add(i);
        }
        // now test the case for S_k
        int[] A = new int[26]; // all S_k starting from the first position
        int mostLeftIndex = -1;// before this position(inclusive), string is tested valid
        for(int i =0;i< s.length();i++){
            char ch = s.charAt(i);
            List<Integer> list = all.get(ch-'a');
            while( A[ch-'a'] < list.size() && list.get(A[ch-'a']) <= mostLeftIndex){
                A[ch-'a'] ++;
            }
            if(A[ch-'a']  == list.size() )
                return false;
            mostLeftIndex = list.get(A[ch-'a']);
            
        }
        return true;
        
    }
}
 

Errors：

Follow up 情况的时候，由于 mostLeftIndex定义的变化， 做比较的时候，忘了加上  <=