792. Number of Matching Subsequences

用户1147447

发布于 2019-05-26 00:41:52

4240

发布于 2019-05-26 00:41:52

文章被收录于专栏：机器学习入门机器学习入门

LWC 74: 792. Number of Matching Subsequences

Problem:

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

思路：从note中可以看出words的长度不长，而S的长度最大有50000，暴力的做法：每个word去匹配S，因为S没有记忆成高效数据结构，每次匹配都会重新遍历一次S，时间复杂度为O(len(S))，显然会超时。

所以我们需要对S进行改造，采用dp[i]['a' ~ 'z']表示在S[i]这个位置后，最先出现’a’ ~ ‘z’的下标。这样我们建立了一个O(1)的索引。可以快速匹配word了。这其中还有贪心的思路，还需细细品味。

Java版本：

    public int numMatchingSubseq(String S, String[] words) {
        int n = S.length();
        int[][] dp = new int[n + 1][32];
        for (int i = 0; i < n + 1; ++i) Arrays.fill(dp[i], -1);
        for (int i = n - 1; i >= 0; --i) dp[0][S.charAt(i) - 'a'] = i + 1;

        for (int j = n - 2; j >= 0; --j) {
            for (int i = 0; i < 32; ++i) {
                dp[j + 1][i] = dp[j + 2][i];
            }
            dp[j + 1][S.charAt(j + 1) - 'a'] = j + 2;
        }

        int cnt = 0;
        for (String word : words) {
            int prv = 0;
            boolean ok = true;
            for (int j = 0; j < word.length(); ++j) {
                int nxt = dp[prv][word.charAt(j) - 'a'];
                if (nxt != -1) {
                    prv = nxt;
                }
                else ok = false;
            }
            if (ok) cnt ++;
        }
        return cnt;
    }

其他思路：参考：https://leetcode.com/problems/number-of-matching-subsequences/discuss/117598/Java-solution-using-HashMap-and-Queue

把words的第一个字符以<character, string>的数据结构存储，接着遍历S中的每一个字符，找到在该字符下的words，删除words的字符，更新word。当word的长度为1时，表示匹配成功，计数。

Java版本：

public int numMatchingSubseq(String S, String[] words) {
        Map<Character, Deque<String>> map = new HashMap<>();
        for (char c = 'a'; c <= 'z'; c++) {
            map.putIfAbsent(c, new LinkedList<String>());
        }
        for (String word : words) {
            map.get(word.charAt(0)).addLast(word);
        }

        int count = 0;
        for (char c : S.toCharArray()) {
            Deque<String> queue = map.get(c);
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.removeFirst();
                if (word.length() == 1) {
                    count++;
                } else {
                    map.get(word.charAt(1)).addLast(word.substring(1));
                }
            }
        }
        return count;
    }

Python版本：

class Solution(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        res = 0
        dic = collections.defaultdict(list)
        for word in words:
            dic[word[0]].append(word)

        for s in S:
            queue = dic[s]
            size = len(queue)
            for i in range(size):
                word = queue.pop(0)
                if len(word) == 1:
                    res += 1
                    continue
                word = word[1:]
                dic[word[0]].append(word)

        return res

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018年03月06日，如有侵权请联系 cloudcommunity@tencent.com 删除

java