本文主要是介绍【C++】每日一题 392 判断子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
直接按照进阶解答：
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;unordered_map<char, vector<int>> buildMap(string t) {unordered_map<char, vector<int>> charMap;for (int i = 0; i < t.length(); ++i) {charMap[t[i]].push_back(i);}return charMap;
}bool isSubsequence(const string& s, const string& t, unordered_map<char, vector<int>>& charMap) {int prevPos = -1;for (char c : s) {if (!charMap.count(c)) return false; // 如果 t 中没有字符 c，则 s 不可能是 t 的子序列auto it = upper_bound(charMap[c].begin(), charMap[c].end(), prevPos); // 在 charMap[c] 中寻找大于 prevPos 的第一个位置if (it == charMap[c].end()) return false; // 如果找不到大于 prevPos 的位置，则 s 不可能是 t 的子序列prevPos = *it;}return true;
}int main() {string t = "ahbgdc";unordered_map<char, vector<int>> charMap = buildMap(t);// 假设有大量的输入 S1, S2, ... , Skvector<string> inputs = {"abc", "ace", "xyz", "agc"};for (const string& s : inputs) {if (isSubsequence(s, t, charMap)) {cout << s << " is a subsequence of " << t << endl;} else {cout << s << " is not a subsequence of " << t << endl;}}return 0;
}时间复杂度分析：
预处理阶段（buildMap 函数）：遍历字符串 t，时间复杂度为 O(n)，其中 n 是字符串 t 的长度。
每次检查子序列阶段（isSubsequence 函数）：对于每个子序列 s，我们只需遍历其字符，时间复杂度为 O(m)，其中 m 是子序列 s 的长度。在查找字符出现的位置时，使用了二分查找，时间复杂度为 O(logn)，其中 n 是字符串 t 的长度。因此，总体时间复杂度为 O(kmlogn)，其中 k 是子序列的数量。
空间复杂度分析：
预处理阶段：使用了一个哈希表 charMap，存储了每个字符出现的位置，最坏情况下需要 O(n) 的额外空间，其中 n 是字符串 t 的长度。
每次检查子序列阶段：除了常量级别的额外空间，主要消耗的空间是哈希表 charMap，因此空间复杂度为 O(n)，其中 n 是字符串 t 的长度。
综上所述，修改后的代码时间复杂度为 O(kmlogn)，空间复杂度为 O(n)。在实际应用中，这种方法可以有效地处理大量子序列的检查，并且时间复杂度和空间复杂度都是可接受的。
这篇关于【C++】每日一题 392 判断子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
