Minimum Window Substring
文章目录
Minimum Window Substring 题解
题目描述
即寻找字符串S的最短子字符串s,使得s包含字符串T中的所有元素。
如:S="ADOBECODEBANC",T="ABC",满足条件的最短子字符串s="BANC"。
题解
问题存在最优子结构性质。设f(i)表示字符串S的子字符串S[1:i]中包含字符串T中的所有元素的最短子字符串,suffix(j)表示字符串S的以S[j]为末的子字符串S[h:j]中包含字符串T中的所有元素的最短子字符串。以上两者若不存在满足条件的子串则为无穷长的字符串。那么f(i+1)=minLen(f(i),suffix(j))。
此题中设字符串S长度为n,字符串T长度为m。答案即f(n)。状态数n个,状态转移复杂度O(1)。而预处理字符串T以建立T中元素映射表只需要扫描一遍T即可。由于是7位ASCII码,因此映射表占用空间为常量(若不是ASCII码,可换成通用哈希表进行映射,空间复杂度为O(m))。因此此题总体时间复杂度为O(max(m,n))。由于解需要O(n)的空间,空间复杂度为O(n)。
代码
class Solution {
static const size_t ASCIISIZE = 128;
public:
string minWindow(string s, string t) {
int has[ASCIISIZE] = { 0 };
size_t fill = t.size(), start = s.size(), end = s.size(), min = std::numeric_limits<size_t>::max();
for (size_t i = fill; i--; )
++has[t[i]];
for (size_t i = s.size(); i--; )
if (has[s[i]]-- > 0)
if (fill == 1) {
while (has[s[--end]]++ != 0) {}
size_t len = end - i + 1U;
if (len < min) {
min = len;
start = i;
}
} else {
--fill;
}
return s.substr(start, min);
}
};
总结
主要应用了动态规划的思想。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论