[LeetCode]Number of Matching Subsequences

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论