题目描述：

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

题目大意：

给定字符串S和字典words，求words中是S的子序列的单词个数。

解题思路：

动态规划（Dynamic Programming）

dp[x][c]表示S[x]之后字符c第一次出现的位置

利用O(len(S))的代价，可以预处理出上述dp数组

对于字典words中的单词word，以O(len(word))的代价可以判断该单词是否为S的子序列

综上，时间复杂度为O(len(S) + len(word) * len(words))

Java代码：

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int slen = S.length();
        int[] last = new int[26];
        int[][] dp = new int[slen + 1][26];
        for (int i = 0; i < slen; i++) {
            int idx = S.charAt(i) - 'a';
            for (int x = last[idx]; x <= i; x++) {
                dp[x][idx] = i + 1;
            }
            last[idx] = i + 1;
        }
        int cnt = 0;
        for (String word: words) {
            cnt += check(dp, word);
        }
        return cnt;
    }

    public int check(int[][] dp, String word) {
        int idx = 0;
        int wlen = word.length();
        for (int i = 0; i < wlen; i++) {
            idx = dp[idx][word.charAt(i) - 'a'];
            if (idx == 0) return 0;
        }
        return 1;
    }
}

 

本文链接：http://bookshadow.com/weblog/2018/03/04/leetcode-number-of-matching-subsequences/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码