题目大意:给你一些单词,问有多少单词出现在字符串S的子序列中。
https://leetcode.com/problems/number-of-matching-subsequences/description/
Given string S
and a dictionary of words words
, find the number of words[i]
that is a subsequence of S
.
1 2 3 4 5 6 |
Example : Input: S = "abcde" words = ["a", "bb", "acd", "ace"] Output: 3 Explanation: There are three words in <code>words</code> that are a subsequence of <code>S</code>: "a", "acd", "ace". |
Note:
- All words in
words
andS
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]
.
Solution 1: Brute Force
Time complexity: O((S + L) * W)
C++ w/o cache TLE
Space complexity: O(1)
C++ w/ cache 155 ms
Space complexity: O(W * L)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Author: Huahua // Running time: 155 ms class Solution { public: int numMatchingSubseq(const string& S, vector<string>& words) { int ans = 0; unordered_map<string, bool> m; for (const string& word : words) { auto it = m.find(word); if (it == m.end()) { bool match = isMatch(word, S); ans += m[word] = match; } else { ans += it->second; } } return ans; } private: bool isMatch(const string& word, const string& S) { int start = 0; for (const char c : word) { bool found = false; for (int i = start; i < S.length(); ++i) if (S[i] == c) { found = true; start = i + 1; break; } if (!found) return false; } return true; } }; |
Solution 2: Indexing+ Binary Search
Time complexity: O(S + W * L * log(S))
Space complexity: O(S)
S: length of S
W: number of words
L: length of a word
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Running time: 183 ms class Solution { public: int numMatchingSubseq(const string& S, vector<string>& words) { vector<vector<int>> pos(128); for (int i = 0; i < S.length(); ++i) pos[S[i]].push_back(i); int ans = 0; for (const string& word : words) ans += isMatch(word, pos); return ans; } private: unordered_map<string, bool> m_; bool isMatch(const string& word, const vector<vector<int>>& pos) { if (m_.count(word)) return m_[word]; int last_index = -1; for (const char c : word) { const vector<int>& p = pos[c]; const auto it = std::lower_bound(p.begin(), p.end(), last_index + 1); if (it == p.end()) return m_[word] = false; last_index = *it; } return m_[word] = true; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Running time: 135 ms class Solution { private List<List<Integer>> pos; private boolean isMatch(String word) { int l = -1; for (char c : word.toCharArray()) { List<Integer> p = pos.get(c); int index = Collections.binarySearch(p, l + 1); if (index < 0) index = -index - 1; if (index >= p.size()) return false; l = p.get(index); } return true; } public int numMatchingSubseq(String S, String[] words) { pos = new ArrayList<>(); for (int i = 0; i < 128; ++i) pos.add(new ArrayList<Integer>()); char[] s = S.toCharArray(); for (int i = 0; i < s.length; ++i) pos.get(s[i]).add(i); int ans = 0; for (String word : words) if (isMatch(word)) ++ans; return ans; } } |
Python 3:
w/o cache
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
""" Author: Huahua Running time: 1120 ms """ class Solution: def numMatchingSubseq(self, S, words): import bisect def isMatch(word): l = -1 for c in word: index = bisect.bisect_left(pos[c], l + 1) if index == len(pos[c]): return 0 l = pos[c][index] return 1 pos = {chr(i + ord('a')) : [] for i in range(26)} for i, c in enumerate(S): pos[c].append(i) return sum(map(isMatch, words)) |
w/ cache
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
""" Author: Huahua Running time: 632 ms """ class Solution: def numMatchingSubseq(self, S, words): import bisect def isMatch(word): if word in m: return m[word] l = -1 for c in word: index = bisect.bisect_left(pos[c], l + 1) if index == len(pos[c]): m[word] = 0 return 0 l = pos[c][index] m[word] = 1 return 1 m = {} pos = {chr(i + ord('a')) : [] for i in range(26)} for i, c in enumerate(S): pos[c].append(i) return sum(map(isMatch, words)) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment