Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S="ADOBECODEBANC"
T="ABC"
Minimum window is"BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
这又是属于繁题,需要处理的情况很多,一不小心就会出错。
本题思路:
利用两个表,以字母为下标,一个记录字母出现的总次数,一个记录当前搜索中出现字母的次数
处理情况:
1 出现重复子字符的情况,中间的重复字符不需要特殊处理,只需要处理最左边的重复字符,最左边的指标往右走。
2 记录当前出现了多少个合法子字符,多次重复出现的算不合法字符,如果合法字符等于子字符长度,那么就是找到一个窗口了。
分情况处理,其实很困难,到底如何可以淡定地应付这一类型的题目呢,目前还没找到很轻松的办法。
string minWindow(string S, string T)
{
int fixedTable[256] = {0};
int countingTable[256] = {0};
int tn = T.length();
for (int i = 0; i < tn; i++)
{
fixedTable[T[i]]++;
}
int minLen = INT_MAX, len = 0;
int Tcount = 0;
int sn = S.length();
string rs("");
//查找子字符串开始的位置
int start = 0;
while (start < sn && fixedTable[S[start]] == 0) start++;
for (int i = start; i < sn; i++)
{
len++;
//查找到相等字符的时候处理
if (fixedTable[S[i]] != 0)
{
//查找到就++
countingTable[S[i]]++;
//处理中间重复字符不计算的情况:
if (countingTable[S[i]] <= fixedTable[S[i]])
{
Tcount++;
}
//增加一个计数,Tcount用来判断是否出现了所有子字符
//处理找到的情况:
if (Tcount == tn)
{
if (len < minLen)
{
minLen = len;
//substr用法,后面的是长度
rs = S.substr(i-len+1, len);
}
//最左边的字符数减一
countingTable[S[i-len+1]]--;
len--;
Tcount--;
//lend==0的时候就是所有字符都减完了,比如在T.length()==1的时候。
while (len>0 && fixedTable[S[i-len+1]] == 0)
{
len--;
}
}
//只需要判断最左边的字符是否重复就可以了
while (countingTable[S[i-len+1]] > fixedTable[S[i-len+1]])
{
//最左边重复字符去掉
countingTable[S[i-len+1]]--;
//Tcount--;最左边重复字符没有计算在Tcount中,不用--
len--;
//非T字符去掉
while (fixedTable[S[i-len+1]] == 0)
{
len--;
}
}
}//if (fixedTable[S[i]] != 0)
}
return rs;
}
下面是我一开始写了的程序,这个程序我假定了中间不会包含重复字符的,所以没通过。
不过题目要求改一改,就用得上这个程序了,故此保留。
//中间不能有重复的程序
string minWindow2(string S, string T)
{
int fixedTable[256] = {0};
int countingTable[256] = {0};
int tn = T.length();
for (int i = 0; i < tn; i++)
{
fixedTable[T[i]]++;
}
int minLen = INT_MAX, len = 0;
int Tcount = 0;
int sn = S.length();
string rs("");
//查找子字符串开始的位置
int start = 0;
while (start < sn && fixedTable[S[start]] == 0) start++;
for (int i = start; i < sn; i++)
{
len++;
//查找到相等字符的时候处理
if (fixedTable[S[i]] != 0)
{
//查找到就++
countingTable[S[i]]++;
Tcount++;
//小于等于固定table说明,是合法增加的子字符
if (countingTable[S[i]] <= fixedTable[S[i]])
{
//增加一个计数,Tcount用来判断是否出现了所有子字符
if (Tcount == tn)
{
if (len < minLen)
{
minLen = len;
//substr用法,后面的是长度
rs = S.substr(i-len+1, len);
}
//最左边的字符数减一
countingTable[S[i-len+1]]--;
len--;
Tcount--;
//lend==0的时候就是所有字符都减完了,比如在T.length()==1的时候。
while (len>0 && fixedTable[S[i-len+1]] == 0)
{
len--;
}
}
}
//重复字符出现次数过多
else
{
while (S[i-len+1] != S[i])
{
if (fixedTable[S[i-len+1]])
{
//注意:别忘记处理countingTalbe
countingTable[S[i-len+1]]--;
Tcount--;
}
len--;
}
//注意三个标志:len, Tcount和countingTable都别忘记处理了
countingTable[S[i]]--;
//等于和不等于的时候,都需要进一步处理len和Tcount
len--;
Tcount--;
while (fixedTable[S[i-len+1]] == 0)
{
len--;
}
}
}//if (fixedTable[S[i]] != 0)
}
return rs;
}
//2014-2-11 update
string minWindow(string S, string T)
{
int A[256] = {0};
int B[256] = {0};
for (int i = 0; i < T.length(); i++) A[T[i]]++;//T[i] or T[i]-'a'
int c = 0;
int begin = 0, len = INT_MAX;
int i = 0;
while (i < S.length() && !A[S[i]]) i++;
for (int j = i; j < S.length(); j++)
{
if (A[S[j]])
{
B[S[j]]++;
if (B[S[j]] <= A[S[j]])
{
if (++c == T.length())//founded
{
if (len > j-i+1)//save result
{
begin = i;
len = j-i+1;
}
--c; --B[S[i]];
for (++i; i<j && (!A[S[i]] || A[S[i]] < B[S[i]]); ++i)
if (A[S[i]]) B[S[i]]--;//i<j防止越界
}
}
else if (S[j] == S[i])//handle repeated
{
B[S[i]]--;
for (++i; i<j && (!A[S[i]] || A[S[i]] < B[S[i]]); ++i)
if (A[S[i]]) B[S[i]]--;
}
}//if (A[idx])...
}//for (int j = i;...
return INT_MAX == len? "":S.substr(begin, len);//当T.length() > S.length()
}
分享到:
相关推荐
leetcode76 LeetCode76_MinimumWindowSubstring
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
leetcode 分类 Leetcode Introduction 本文旨在将leetcode的题型分类 Pattern: Sliding window 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口...
java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...LeetCode ...Substring Without Repeating Characters LeetCode 13 Roman to Integer LeetCode 6 Zi
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
411 | [Minimum Unique Word Abbreviation](https://leetcode.com/problems/minimum-unique-word-abbreviation/) | [C++](./C++/minimum-unique-word-abbreviation.cpp) [Python](./Python/minimum-unique-word-...
Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a ...
leetcode中文版
vs code LeetCode 插件
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...