专业烟台房产网站建设,广东东莞石碣今天新闻,可以做国外购物的网站有哪些,西安建站免费模板题目链接 剑指 Offer II 017. 含有所有字符的最短字符串 hard 题目描述
给定两个字符串 s和 t。返回 s中包含 t的所有字符的最短子字符串。如果 s中不存在符合条件的子字符串#xff0c;则返回空字符串 。
如果 s中存在多个符合条件的子字符串#xff0c;返回任…题目链接 剑指 Offer II 017. 含有所有字符的最短字符串 hard 题目描述
给定两个字符串 s和 t。返回 s中包含 t的所有字符的最短子字符串。如果 s中不存在符合条件的子字符串则返回空字符串 。
如果 s中存在多个符合条件的子字符串返回任意一个。
注意 对于 t中重复字符我们寻找的子字符串中该字符数量必须不少于 t中该字符数量。
示例 1 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’ 示例 2 输入s “a”, t “a” 输出“a” 示例 3 输入s “a”, t “aa” 输出“” 解释t 中两个字符 ‘a’ 均应包含在 s 的子串中因此没有符合条件的子字符串返回空字符串。 提示
1s.length,t.length1051 s.length, t.length 10^51s.length,t.length105s和 t由英文字母组成
分析
本题用 滑动窗口 求解。
用哈希表 ht记录 t中字符的出现次数。
再用另一个哈希表 hs记录 s滑动窗口区间的字符出现次数。
用两个指针 i和 j分别维护滑动窗口的左边界 和 右边界。
如果 hs[s[j]] ht[s[j]]说明此时的 s[j]依旧是有效字符区间有效字符数 cnt 1。
如果 hs[s[i]] ht[s[i]]说明此时的区间内部字符已经超过了 t所以收缩左区间hs[s[i]]--i。
如果 cnt t.size()说明此时的区间 [l,r]包含了 t的所有字符所以此时的 s.substr(i,j-i1)可作为答案之一。
时间复杂度 O(n)O(n)O(n)
代码
class Solution {
public:string minWindow(string s, string t) {int m s.size() , n t.size();if(m n) return ;unordered_mapchar,int ht,hs;for(auto c:t) ht[c];int len 1e9,idx -1;int cnt 0;for(int i 0,j 0;j m;j){hs[s[j]];if(hs[s[j]] ht[s[j]]) cnt;while(hs[s[i]] ht[s[i]]){hs[s[i]]--;i;}if(cnt n){if(j - i 1 len){idx i;len j - i 1;}}}return idx -1 ? : s.substr(idx,len);}
};
