LeetCode -- 792. 匹配子序列的单词数

 方法1：利用桶的思想同时匹配所有words中的子串 (走路写法)

把所有首字母相同的子串放入到一个桶中，然后遍历s，对于首字母为s[i]的单词，若其大小为1则res ++, 否则删掉s[i]，并根据s[i + 1]放入新的桶中。

c ++ 
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<queue<string>> d(26);
        for(auto &w : words) {
            d[w[0] - 'a'].push(w);
        }

        int res = 0;
        for(auto &c : s) {
            auto &q = d[c - 'a'];
            for(int i = q.size(); i; i -- ) {
                auto t = q.front();
                q.pop();
                if(t.size() == 1) res ++ ;
                else d[t[1] - 'a'].push(t.substr(1));
            }
        }
        return res;
    }
};

方法二 ：地址哈希与二分查找  (自行车写法)

我们把每个字母的下标进行映射，pos[0] 及所有 'a'字符在s中的下标，并这些下标有小到大排序。

对于每个word子串，用upper_bound()遍历其每个字符的位置，当有字符的位置为pos[i].end()时，表示不存在，及word不是s的子串。

c ++ 
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>> pos(26);

        for(int i = 0; i < s.size(); i ++ ) {
            pos[s[i] - 'a'].push_back(i);
        }

        int res = words.size();
        for(auto &word : words) {
            if(word.size() > s.size()) {
                res -- ;
                continue;
            }

            int p = -1;
            for(auto c : word) {
                auto &ps = pos[c - 'a'];
                auto it = upper_bound(ps.begin(), ps.end(), p);
                if(it == ps.end()) {
                    res -- ;
                    break;
                }
                p = *it;
            }
        }
        return res;

    }
};

方法三:桶 + 多指针   (摩托车写法)

我们对每个子串记录一个类似文件指针的字符指针，该指针指向了当前遍历到了子串的什么位置

当字符指针的值为word.size()时，res ++ ；否则将该字符串加入对应的桶中

c ++ 
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<queue<pair<int, int>>> queues(26);
        for(int i = 0; i < words.size(); i ++ ) {
            queues[words[i][0] - 'a'].push({i, 0});
        }

        int res = 0;
        for(auto c : s) {
            auto &q = queues[c - 'a'];
            int sz = q.size();
            while(sz -- ) {
                auto [i, j] = q.front();
                q.pop();
                j ++ ;
                if(j == words[i].size()) {
                    res ++ ;
                } else {
                    queues[words[i][j] - 'a'].push({i, j});
                }
            }
        }

        return res;
    }
};

java
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Queue<int[]>[] p = new Queue[26];
        for(int i = 0; i < 26; i ++ ) {
            p[i] = new ArrayDeque<int[]>();
        }

        for(int i = 0; i < words.length; i ++ ) {
            p[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});
        }

        int res = 0;
        for(int i = 0; i < s.length(); i ++ ) {
            char c = s.charAt(i);
            int len = p[c - 'a'].size();
            while(len > 0) {
                int[] t = p[c - 'a'].poll();
                if(t[1] == words[t[0]].length() - 1) {
                    res ++ ;
                } else {
                    t[1] ++ ;
                    p[words[t[0]].charAt(t[1]) - 'a'].offer(t);
                }
                len -- ;
            }
        }
        return res;
    }
}

python
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        p = defaultdict(list)
        for i, w in enumerate(words):
            p[w[0]].append((i, 0))

        res = 0
        for c in s:
            q = p[c]
            p[c] = []
            for i, j in q:
                j += 1
                if j == len(words[i]):
                    res += 1
                else:
                    p[words[i][j]].append((i, j))

        return res

js
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var numMatchingSubseq = function(s, words) {
    let p = new Array(26).fill(0).map(() => new Array());
    for(let i = 0; i < words.length; i ++ ) {
        p[words[i][0].charCodeAt() - 'a'.charCodeAt()].push([i, 0]);
    }

    let res = 0;
    for(let i = 0; i < s.length; i ++ ) {
        let c = s[i];
        let len = p[c.charCodeAt() - 'a'.charCodeAt()].length;

        while(len > 0) {
            len -- ;
            let t = p[c.charCodeAt() - 'a'.charCodeAt()].shift();
            if(t[1] === words[t[0]].length - 1) {
                res ++ ;
            } else {
                t[1] ++ ;
                p[words[t[0]][t[1]].charCodeAt() - 'a'.charCodeAt()].push(t);
            }
        }
    }
    return res;
};

golang
func numMatchingSubseq(s string, words []string) int {
    type pair struct {
        i int
        j int
    }

    ps := [26][]pair{}
    for i, w := range words {
        ps[w[0] - 'a'] = append(ps[w[0] - 'a'], pair{i, 0})
    }

    res := 0
    for _, c := range s {
        q := ps[c - 'a']
        ps[c - 'a'] = nil
        for _, p := range q {
            p.j ++ 
            if p.j == len(words[p.i]) {
                res ++ 
            } else {
                w := words[p.i][p.j] - 'a'
                ps[w] = append(ps[w], p)
            }
        }
    }
    return res
}