title
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”.
solution
求subsequence的数目，
定义 nxtPosn, 其中 nxtPosi 表示串S的第i个位置起, 下标最靠前的字符 j + ‘a’ 的位置.
借助 nxtPos 数组我们可以在 O(word.length) 的时间内判断出 word 是否 S 的子序列.
而我们对 S 进行一次遍历就可以求出 nxtPos 数组.
class Solution:
"""
@param S: a string
@param words: a dictionary of words
@return: the number of words[i] that is a subsequence of S
"""
def numMatchingSubseq(self, S, words):
self.idx = { 'a' : 0, 'b' : 1, 'c' : 2, 'd' : 3, 'e' : 4,
'f' : 5, 'g' : 6, 'h' : 7, 'i' : 8, 'j' : 9,
'k' : 10, 'l' : 11, 'm' : 12, 'n' : 13, 'o' : 14,
'p' : 15, 'q' : 16, 'r' : 17, 's' : 18, 't' : 19,
'u' : 20, 'v' : 21, 'w' : 22, 'x' : 23, 'y' : 24, 'z' : 25 }
n = len(S)
nxtPos = []
tmp = [-1] * 26
for i in range(n - 1, -1, -1):
tmp[self.idx[S[i]]] = i
nxtPos.append([i for i in tmp])
nxtPos = nxtPos[::-1]
ans = 0
for word in words:
if self.isSubseq(word, nxtPos):
ans += 1
return ans
def isSubseq(self, word, nxtPos):
lenw = len(word)
lens = len(nxtPos)
i, j = 0, 0
while i < lenw and j < lens:
j = nxtPos[j][self.idx[word[i]]]
if j < 0:
return False
i += 1
j += 1
return i == lenw
这个就是先缓存起来，提高效率
class Solution {
public:
bool f(string &a, string b) {
if (a.size() > b.size()) {
return false;
}
int i = 0;
for (auto it : b) {
if (a[i] == it) {
i++;
}
if (i == a.size())
return true;
}
return false;
}
int numMatchingSubseq(string S, vector<string>& words) {
int res = 0;
unordered_set<string> in, out;
for (auto it : words) {
if (in.count(it) || out.count(it)) {
if (in.count(it)) {
res++;
}
continue;
}
if (f(it, S)) {
res++;
in.insert(it);
}
else {
out.insert(it);
}
}
return res;
}
o(n2logn)
// General Idea:
// - Brute force checking will time out, we need efficent way to look up words
// - Create an vector that stores indices for each character a-z in S
// - Then for each word, do a binary search for next index for current character in word
// that is greater than the index we last found for the alst character
// - If it doesn't exist, word doesn't exist, otherwise continue to search for word
int numMatchingSubseq (string S, vector<string>& words) {
vector<vector<int>> alpha (26);
for (int i = 0; i < S.size (); ++i) alpha[S[i] - 'a'].push_back (i);
int res = 0;
for (const auto& word : words) {
int x = -1;
bool found = true;
for (char c : word) {
auto it = upper_bound (alpha[c - 'a'].begin (), alpha[c - 'a'].end (), x);
if (it == alpha[c - 'a'].end ()) found = false;
else x = *it;
}
if (found) res++;
}
return res;
}
First, we store all characters’ positions of input. For example: input = “abacbca” —> POS = [‘a’, ‘b’, ‘c’] = [ [0,2,6], [1,4], [3,5] ]
Second, while iterating words, for each character of each word, we check if we can choose a position from POS, and the position must follow an increasing order. For example: word = “acb” ‘a’ we choose 0 ‘c’ we choose 3 ‘b’ we choose 4 [0,3,4] is an increasing order, so “acb” is a subsequence of our input.
Third, we store the position of current iterating character in a variable cur. The next iteration, we will chose the position so that it’s value > cur by using Binary Search
public int numMatchingSubseq(String s, String[] words) {
int res = 0, cur, i;
List<Integer>[] pos = positions(s);
for (String w : words) {
for (i = 0, cur = 0; i < w.length(); i++, cur++) {
char c = w.charAt(i);
cur = search(pos[c-'a'], cur);
if (cur == -1) break;
}
if (cur != -1) res++;
}
return res;
}
private List<Integer>[] positions(String s) {
List<Integer>[] pos = new List['z'-'a'+1];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (pos[c-'a'] == null) pos[c-'a'] = new ArrayList<>();
pos[c-'a'].add(i);
}
return pos;
}
private int search(List<Integer> ns, int n) {
if (ns == null) return -1;
int lo = 0, hi = ns.size()-1;
if (ns.get(lo) >= n) return ns.get(lo);
if (ns.get(hi) < n) return -1;
while (lo < hi) {
int mi = (lo + hi)/2;
if (ns.get(mi) == n) return ns.get(mi);
if (ns.get(mi) < n) lo = mi+1;
else hi = mi;
}
return ns.get(hi);
}