# 792. 匹配子序列的单词数

力扣原题链接(点我直达) (opens new window)

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

示例:
输入: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
1
2
3
4
5
6

注意:

  • 所有在wordsS 里的单词都只由小写字母组成。
  • S 的长度在 [1, 50000]
  • words 的长度在 [1, 5000]
  • words[i]的长度在[1, 50]

# 第一版 emmmm...自己写的,很差

执行用时 :1136 ms, 在所有 cpp 提交中击败了5.05%的用户

内存消耗 :136 MB, 在所有 cpp 提交中击败了18.75%的用户

int numMatchingSubseq(string S, vector<string>& words) {

	unordered_map<char, set<int>> mp;
	for (unsigned i = 0; i < S.size(); ++i) {
		mp[S[i]].insert(i);
	}

	int count = 0,temp;
	unsigned i = 0;
	for (auto& word : words) {
		temp = *(mp[word[0]].begin());		
		for (i = 1; i < word.size(); ++i) {
			auto pos = mp[word[i]].upper_bound(temp);
			if (pos != mp[word[i]].end()) {

				if (*pos > temp) temp = *pos;
				else
					break;
			}
			else
				break;

		}

		if (i == word.size()) count++;

	}
	return count;

}
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

# 第二版,稍微改进一下

执行用时 :308 ms, 在所有 cpp 提交中击败了58.08%的用户

内存消耗 :40.5 MB, 在所有 cpp 提交中击败了65.63%的用户

int numMatchingSubseq(string S, vector<string>& words) {
	

	unordered_map<char, vector<int>> mp;
	for (unsigned i = 0; i < S.size(); ++i) {
		mp[S[i]].push_back(i);
	}

	int count = 0,temp;
	unsigned i;
	for (auto& word : words) {
		if (mp.find(word[0]) == mp.end()) //时刻注意判断问题
			continue;
		temp = *(mp[word[0]].begin());
		for (i = 1; i < word.size(); ++i) {
			if (mp.find(word[i]) == mp.end()) //时刻注意判断有无问题
				break;
			auto pos = upper_bound(mp[word[i]].begin(), mp[word[i]].end(),temp);
			if (pos != mp[word[i]].end()) {
				temp = *pos;
			}
			else
				break;
		}
		if (i==word.size()) count++;
	}
	return count;

}

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