首页 > itarticle > [leetcode] problem 792 – number of matching subsequences

[leetcode] problem 792 – number of matching subsequences

admin 11月 13, 2020 0

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

public int (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;
}