leetcode 792. Number of Matching Subsequences

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].

思路:先用vector记录每个字母出现的位置，然后遍历每个单词，如果每个字母的位置是递增的那么这个单词就符合要求。如何判断位置见的递增关系呢？可以用二分实现。具体看代码

class Solution {

public:

    int numMatchingSubseq(string S, vector<string>& words) {

        vector<int> v[26];

        for (int i = 0; i < S.size(); ++i) {

            v[S[i]-'a'].emplace_back(i);

        }

        int ans = 0;

        for (auto i : words) {

            int mark = 0;

            int y = -1;

            for(auto c : i) {

                int x = c - 'a';

                if (v[x].empty()) {

                    mark = 1; break;

                }

                int pos = upper_bound(v[x].begin(), v[x].end(), y) - v[x].begin();

                if (pos < v[x].size()) {

                    y = v[x][pos];

                } else {

                    mark = 1; break;

                }

            }

            if (!mark) ans++;

        }

        return ans;

    }

};

巴特西

leetcode 792. Number of Matching Subsequences

最新文章

热门文章