792. Number of Matching Subsequences

because this problem's bottle neck is the s length, 5*10^4, so how to optimized in this is the key.

Naive Solution - two poniters, TLE, because s is too big

s = "abcde", words = ["a","bb","acd","ace"]

abcde
j

acd
i

time: O(n*m), , m is s length, n is words size(), m is so big

space: O(1)

移動雙指針去找是否 match

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            if (isMatching(word, s)) {
                count++;
            }
        }
        return count;
    }
    private boolean isMatching(String word, String s) {
        int i = 0;
        int j = 0;
        while (i < word.length() && j < s.length()) {
            if(word.charAt(i) == s.charAt(j)) {
                i++;
                j++;
            } else {
                j++;
            }
        }
        return i == word.length();
    }
}

two pointer + hashset

這個解法可以過, 通過率還相當不錯...

應該是因為太多重複的字需要判斷, 所以把 pass 的字, not pass 的字都 memo 一下, 效率就差很多了

time: O(n*m), , m is s length, n is words size(), m is so big

space: O(n)

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        Set<String> pass = new HashSet<>();
        Set<String> notPass = new HashSet<>();
        for (String word : words) {
            if (isSubseq(s, word, pass, notPass)) {
                count++;
            }
        }
        return count;
    }
    private boolean isSubseq(String s, String word, Set<String> pass, Set<String> notPass) {

        if (pass.contains(word)) {
            return true;
        }
        if (notPass.contains(word)) {
            return false;
        }
        
        int i = 0;
        int j = 0;
        while (i < s.length() && j < word.length()) {
            if (s.charAt(i) != word.charAt(j)) {
                i++;
            } else {
                i++;
                j++;
            }
        }
        if (j == word.length()) {
            pass.add(word);
            return true;
        }
        notPass.add(word);
        return false;
    }
}

Binary search

time: O(m + n*wlen*log(m) ), m is s length, n is words size(), wLen is each word len (in words)

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int res = 0; 
        List<Integer>[] pos = positions(s);
        
        for (String w : words) {
            if (isSubseq(w, pos)) {
                res++;
            }
        }
        return res;
    }
    
    private boolean isSubseq(String w, List<Integer>[] pos) {
        int cur = 0;
        for (int i = 0; i < w.length(); i++) {
            char c = w.charAt(i);
            cur = search(pos[c-'a'], cur); 
            if (cur == -1) {
                return false;
            }
            cur++;
        }
        return true;
    }
	
    private List<Integer>[] positions(String s) {
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (pos[c-'a'] == null) {
                pos[c-'a'] = new ArrayList<>();
            }
            pos[c-'a'].add(i);
        }
        return pos;
    }
	
    private int search(List<Integer> list, int n) {
        if (list == null) {
            return -1;
        }
        int start = 0;
        int end = list.size() - 1;
        
        if (list.get(start) >= n) {
            return list.get(start);
        }
        if (list.get(end) < n) { 
            return -1;
        }
        
        while (start < end) {
            int mid = start + (end - start)/2;

            if (list.get(mid) < n) {
                start = mid+1;
            } else {
                end = mid;
            }
        }
        return list.get(start);
    }
  

}

state machine, next letter pointers

int[][] next = new int[m+1][26]

record string each char's index pointer to next char (from a~z),  
next[cur_index(小)][26] = next_index（大）

just link with non-negtive number, if -1 means no pointer

tricky part link with 1-based index, but save with 0 indexed base
s = "#"+s;

      12345
 s = "abcde"

[4][a~z] = -1
[4][e] = 5 (self)

[3][a] = -1
...
[3][d] = 4
[3][e] = 5
...
[2][c] = 3
[2][d] = 4
[2][e] = 5
...
[1][b] = 2
[1][c] = 3
[1][d] = 4
[1][e] = 5
..
[0][a] = 1
[0][b] = 2
[0][c] = 3
[0][d] = 4
[0][e] = 5

概念有點像 trie

so if there is a word: "acd"

    private boolean isSubseq(String word, int[][] next) {
        int start = 0;
        for (char c : word.toCharArray()) {
            start = next[start][c-'a']; // next[0][a] = 1, next[1][c] = 3,  next[3][d] = 4
            if (start == -1) {
                return false;
            }
        }
        return true;
    }

like this

time: O(26m + n*wLen), m is s length, n is words size(), wLen is each word len (in words)

space: O(26m)

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int m = s.length();
        int[][] next = new int[m+1][26];
        s = "#" + s;
        
        for (int k = 0; k < 26; k++) {
            next[m][k] = -1;   
        }
        
        for (int i = m; i >= 1; i--) {
            for (int k = 0; k < 26; k++) {
                next[i-1][k] = next[i][k];
                char c = s.charAt(i);
                next[i-1][c -'a'] = i;
            }
        }
        
        int count = 0;
        for (String word : words) {
            if (isSubseq(word, next)) {
                count++;
            }
        }
        return count;
    }
    private boolean isSubseq(String word, int[][] next) {
        int start = 0;
        for (char c : word.toCharArray()) {
            start = next[start][c-'a'];
            if (start == -1) {
                return false;
            }
        }
        return true;
    }
}

1/4 version

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int m = s.length();
        s = "#"+s;
        int[][] next = new int[m+1][26];
        
        // init last one
        for (int i = 0; i < 26; i++) {
            next[m][i] = -1;
        }
        // from end to init
        for (int i = m; i >= 1; i--) {
            for (int j = 0; j < 26; j++) {
                next[i-1][j] = next[i][j]; // next[m][j] init before, i-1 copy from i
                
                char c = s.charAt(i);
                next[i-1][c-'a'] = i; // = i (m to 1), next[0~m-1][26] = (1~m)
            }
        }
        int count = 0;
        for (String word : words) {
            if (isMatch(word, next)) {
                count++;
            }
        }
        return count;
    }
    private boolean isMatch(String word, int[][] next) {
        int index = 0;
        for (char c : word.toCharArray()) {
            index = next[index][c - 'a'];
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}