手机网站的优缺点,桐城住房和城乡建设局网站,wordpress qux,凡科建站教程76. 最小覆盖子串
给你一个字符串 s s s、一个字符串 t t t。返回 s s s 中涵盖 t t t 所有字符的最小子串。如果 s s s 中不存在涵盖 t t t 所有字符的子串#xff0c;则返回空字符串 ‘ ‘ \quad ‘‘ 。
注意#xff1a;
对于 t t t 中重复…76. 最小覆盖子串
给你一个字符串 s s s、一个字符串 t t t。返回 s s s 中涵盖 t t t 所有字符的最小子串。如果 s s s 中不存在涵盖 t t t 所有字符的子串则返回空字符串 ‘ ‘ \quad ‘‘ 。
注意
对于 t t t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t t t 中该字符数量如果 s s s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2
输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3:
输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。个人解题思路
我们可以利用“滑动窗口”的思想来解决这个问题。 具体步骤如下
初始化
创建一个字典 remaining_target记录字符串 t 中每个字符的出现次数。定义两个指针 index 和 temp_index表示当前窗口的左右边界。定义变量 current_substring用于记录当前窗口的子串。定义变量 min_substring用于记录最小子串。定义变量 min_substring_length用于记录最小子串的长度。定义布尔变量 found_all_chars表示是否已找到目标字符串的所有字符。
遍历字符串
代码首先初始化了目标字符串 t 的临时变量 remaining_target并设置了变量来记录当前子串和最小子串。接着代码遍历源字符串 s对每个字符进行判断它是否在 remaining_target 中。如果在则表示找到了目标字符串中的一个字符remaining_target 中对应字符的数量减一。当在s 中找到第一个 t 的元素时代码记录下当前的索引 temp_index以备后续滑动index使用。 在遍历过程中代码不断更新当前子串 current_substring并在满足条件时更新最小子串 min_substring。当 remaining_target 的长度为零时说明当前窗口已经包含了目标字符串的所有字符代码会通过调整索引来优化子串的长度。最终代码返回找到的最小子串。
python代码
class Solution:def minWindow(self, s: str, t: str) - str:# 初始化目标字符串的副本remaining_target t# 初始化当前子串和最小子串current_substring min_substring min_substring_length len(s)# 标记是否已找到目标字符串的所有字符found_all_chars Falseindex 0# 如果源字符串的长度小于目标字符串直接返回空字符串if len(s) len(t):return # 遍历源字符串while index len(s):current_char s[index]index 1# 如果当前字符在目标字符串中if current_char in remaining_target:found_all_chars True# 删除目标字符串中对应的字符remaining_target remaining_target.replace(current_char, , 1)# 如果目标字符串中剩余字符的长度为目标字符串长度减一记录当前索引if len(remaining_target) len(t) - 1:temp_index index# 如果已找到目标字符串的所有字符if found_all_chars:current_substring current_char # 将当前字符添加到当前子串# 如果目标字符串的所有字符都已找到且当前子串长度小于最小子串长度if len(remaining_target) 0 and len(current_substring) min_substring_length:min_substring current_substringmin_substring_length len(min_substring)# 如果目标字符串的所有字符都已找到if len(remaining_target) 0:index temp_indexremaining_target tfound_all_chars Falsecurrent_substring return min_substring
时间复杂度
时间复杂度 O ( n ) O(n) O(n) 其中 n 是字符串 s s s 的长度。 由于每个字符最多被指针 index 访问一次因此时间复杂度为 O ( n ) O(n) O(n)。空间复杂度 O ( k ) O(k) O(k) 其中 k 是字符集 t t t 的大小。 需要额外的空间来存储字符串 remaining_target 和 current_substring其大小与字符集的大小成正比。
结果
python3的代码在用例165/168处提示超时因此我用deepseek将代码转成了C的形式提交了。以下是C的提交结果和代码C的代码我没有检查
#include string
#include unordered_map
#include algorithmclass Solution {
public:std::string minWindow(std::string s, std::string t) {// 统计 t 中每个字符的出现次数std::unordered_mapchar, int t_count;for (char c : t) {t_count[c];}// 记录当前窗口内每个字符的出现次数std::unordered_mapchar, int window_count;int required t_count.size(); // 需要匹配的字符种类数int formed 0; // 当前窗口内已匹配的字符种类数int left 0, right 0; // 滑动窗口的左右指针int min_len s.size() 1; // 最小窗口的长度int min_left 0; // 最小窗口的左指针while (right s.size()) {// 扩展窗口char c s[right];window_count[c];if (t_count.find(c) ! t_count.end() window_count[c] t_count[c]) {formed;}// 收缩窗口while (left right formed required) {c s[left];if (right - left 1 min_len) {min_len right - left 1;min_left left;}window_count[c]--;if (t_count.find(c) ! t_count.end() window_count[c] t_count[c]) {formed--;}left;}right;}return min_len s.size() 1 ? : s.substr(min_left, min_len);}
};
官方解题思路
其核心思想也是使用滑动窗口的思想结合哈希表来找到字符串 s s s 中包含字符串 t t t 所有字符的最小子串。
初始化
使用 unordered_map ori 来记录目标字符串 t 中每个字符的出现次数。定义两个指针 l 和 r分别表示当前窗口的左边界和右边界。定义变量 len 来记录当前找到的最小子串的长度ansL 和 ansR 分别记录最小子串的起始和结束位置。
遍历字符串
首先右指针 r 向右移动扩展窗口直到窗口包含目标字符串 t 中的所有字符。每次右指针移动时更新当前窗口中字符的计数。当窗口包含了 t 中所有字符时尝试通过移动左指针 l 来收缩窗口寻找更小的覆盖子串。每次收缩时更新当前窗口中字符的计数。在每次收缩窗口时检查当前窗口的大小是否小于之前记录的最小子串长度。如果是则更新最小子串的起始和结束位置。遍历完成后返回从 ansL 到 ansR 的子串。如果未找到符合条件的子串则返回空字符串。
class Solution {
public:unordered_map char, int ori, cnt;bool check() {for (const auto p: ori) {if (cnt[p.first] p.second) {return false;}}return true;}string minWindow(string s, string t) {for (const auto c: t) {ori[c];}int l 0, r -1;int len INT_MAX, ansL -1, ansR -1;while (r int(s.size())) {if (ori.find(s[r]) ! ori.end()) {cnt[s[r]];}while (check() l r) {if (r - l 1 len) {len r - l 1;ansL l;}if (ori.find(s[l]) ! ori.end()) {--cnt[s[l]];}l;}}return ansL -1 ? string() : s.substr(ansL, len);}
};时间复杂度
时间复杂度 O ( n ) O(n) O(n) 其中 n 是字符串 s 的长度。 由于每个字符最多被指针 l 和 r 各访问一次因此时间复杂度为 O ( n ) O(n) O(n)。空间复杂度 O ( k ) O(k) O(k) 其中 k 是字符集的大小。 需要额外的空间来存储哈希表 ori其大小与字符集的大小成正比。
结果 算法分析
同样的思路我的算法要比官方题解效率更高主要可能有以下两方面的原因
数据结构的选择
官方题解 使用了 unordered_map 来记录字符的出现次数。 我的算法 使用了更高效的数据结构即临时变量和数组。 影响 对于字符集大小固定的情况使用临时变量数组可以减少哈希计算的开销从而提高效率。
字符串操作
官方题解 每次收缩窗口时会频繁地进行字符串截取操作。 我的算法通过记录子串的起始位置和长度避免了多次字符串截取。 影响 减少字符串操作可以降低时间复杂度提升性能。
