本文涉及的基础知识点
C++二分查找
贪心
LeetCode792. 匹配子序列的单词数
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是none),而不改变其余字符的相对顺序。
例如, “ace” 是 “abcde” 的子序列。
示例 1:
输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。
示例 2:
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2
提示:
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小^写字母组成。
C++二分查找+贪心
如果word[i]是s的子序列,那word[i][0]一定匹配s的第一个word[i][0],下面用决策包容性来证明。
令s[i1][0]和s[i2][0]都和word[i][0]相等,且i1<i2。如果s[i2+1…]包扩word[i][1…],则s[i1+1…]一定包括word[i][1…]。
indexs[i]记录所有’a’+i的下标。
pos记录已经匹配的位置。
通过j枚举word[i]
在indexs[wrod[i][j]-‘a’]中寻找,大于pos的最小下标,即upower
时间复杂度:O(mlogn) , n = s.length ,m = sum(wrod[i].length)
代码
核心代码
class Solution {public:int numMatchingSubseq(string s, vector<string>& words) {vector<int> indexs[26];for (int i = 0; i < s.length(); i++) {indexs[s[i] - 'a'].emplace_back(i);}auto Is = [&](const string& t) {int pos = -1;for (const auto& ch : t) {const auto& inx = indexs[ch - 'a'];auto it = std::upper_bound(inx.begin(), inx.end(), pos);if (inx.end() == it) { return false; }pos = *it;}return true;};int ret = 0;for (const auto& t : words) {ret += Is(t);}return ret;}};
单元测试
string s; vector<string> words;TEST_METHOD(TestMethod11){s = "abcde", words = { "a", "bb", "acd", "ace" };auto res = Solution().numMatchingSubseq(s, words);AssertEx(3, res);}TEST_METHOD(TestMethod12){s = "dsahjpjauf", words = { "ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax" };auto res = Solution().numMatchingSubseq(s, words);AssertEx(2, res);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。