# 792. Number of Matching Subsequences

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FhtiI8h94sLU6ixUoJzFi%2F%E5%9C%96%E7%89%87.png?alt=media\&token=44daff25-1145-4480-8e63-29e97d3cd0c0)

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

```java
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)

```java
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)

```java
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 p**ointers**

```
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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FkWdV54EY44jUxxER67wZ%2Fimage.png?alt=media\&token=edaf5601-7275-480a-8775-75a6730de3d2)

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

space: O(26m)

```java
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

```java
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;
    }
}


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/state-machine-or-binary-search/792.-number-of-matching-subsequences.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.