[数据结构与算法]LeetCode 792 Number of Matching Subsequences （二分或队列）

Given a string?s?and an array of strings?words, return?the number of?words[i]?that is a subsequence of?s.

A?subsequence?of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example,?"ace"?is a subsequence of?"abcde".

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s?and?words[i]?consist of only lowercase English letters.

题目链接：https://leetcode.com/problems/number-of-matching-subsequences/

题目大意：求words中有多少是字符串s的子序列

题目分析：枚举words中的字符串判断，可预处理s中每个字符的下标位置，判断时二分查找大于等于当前位置的相等字符的下标

80ms，时间击败61.73%

class Solution {
    
    private int find(int pos, List<Integer> list) {
        int n = list.size(), ans = -1;
        int l = 0, r = n - 1, mid = 0;
        while (l <= r) {
            mid = (l + r) >> 1;
            int val = list.get(mid);
            if (val > pos) {
                ans = val;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
    
    private boolean ok(String s, List[] chars) {
        int curPos = -1;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (chars[idx] == null) {
                return false;
            }
            curPos = find(curPos, chars[idx]);
            if (curPos == -1) {
                return false;
            }
        }
        return true;
    }
    
    public int numMatchingSubseq(String s, String[] words) {
        List<Integer>[] chars = new List[26];
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            int idx = str[i] - 'a';
            if (chars[idx] == null) {
                chars[idx] = new ArrayList<Integer>(); 
            }
            chars[idx].add(i);
        }
        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            if (ok(words[i], chars)) {
                ans++;
            }
        }
        return ans;
    }
}

给26个字母每个字母建一个队列，用这些队列来记录s和words中字符串的字符顺序，枚举字符串s的每个字符并取得对应队列，将队列记录的字符串下标后移，移到末尾则答案加1，很巧妙的数据结构的运用

28ms，时间击败99.20%

class Solution {
    
    private class Str {
        String s;
        int pos;
        Str(String s, int pos) {
            this.s = s;
            this.pos = pos;
        }
        
        boolean isEnd() {
            return this.pos == this.s.length() - 1;
        }
    }
    
    public int numMatchingSubseq(String s, String[] words) {
        int ans = 0;
        Queue<Str>[] qs = new LinkedList[26];
        for (int i = 0; i < 26; i++) {
            qs[i] = new LinkedList<>();
        }
        for (int i = 0; i < words.length; i++) {
            qs[words[i].charAt(0) - 'a'].add(new Str(words[i], 0));
        }
        for (char c : s.toCharArray()) {
            Queue<Str> q = qs[c - 'a'];
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                Str cur = q.poll();
                if (cur.isEnd()) {
                    ans++;
                } else {
                    cur.pos++;
                    qs[cur.s.charAt(cur.pos) - 'a'].add(cur);
                }
            }
        }
        return ans;
    }
}