[LeetCode] Problem 792 - Number of Matching Subsequences

Posted on | In ,

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example

Input:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]

Output: 3

Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.

Note

  • All words in words and S will only consists of lowercase letters.
  • The length of S will be in the range of [1, 50000].
  • The length of words will be in the range of [1, 5000].
  • The length of words[i] will be in the range of [1, 50].

Code

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
33
34
35
36
public int numMatchingSubseq(String S, String[] words) {
    List<List<Integer>> pos = new ArrayList<>();
    int result = 0;

    for (int i = 0; i < 26; i++)
        pos.add(new ArrayList<>());

    for (int i = 0; i < S.length(); i++)
        pos.get(S.charAt(i) - 'a').add(i);

    for (String word : words) {
        if (match(pos, word))
            result++;
    }

    return result;
}

private boolean match(List<List<Integer>> pos, String word) {
    int prev = -1;

    for (char ch : word.toCharArray()) {
        List<Integer> list = pos.get(ch - 'a');
        int current = Collections.binarySearch(list, prev + 1);
        
        if (current < 0)
            current = - current - 1;
            
        if (current >= list.size())
            return false;

        prev = list.get(current);
    }

    return true;
}