注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex76 Minimum Window Substring  

2015-05-26 22:48:55|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


这题刚开始没有思路,特别冤,因为他和ex209几乎是一模一样的,无非就是前后两个指针扫描,一旦扫到一个,start指针收缩,当window里面不满足条件的时候,end指针往后挪。统计字符的时候,开一个256大小的数组,这样查找就比较快了~~

/*
* 窗口滑动的问题,和ex209 极为相似
* 可以理解为一旦得到了当前匹配的字符串,左边的指针右移
* 接着判断是否还能找到,如果能找到继续start指针滑动
* 如果不能找到end指针后移
*
* 在ex209中也是窗口滑动,window之间不断求和,一旦大于给定值,start开始收缩
*/
class Solution {
public:
int range = 128;
string minWindow(string s, string t) {

vector<int>pattern(range,0); //这个用来存放t里面出现的频率
vector<int>text(range, 0);

int i;
for (i = 0; i < t.size(); i++)
pattern[t[i]]++;
int start = 0, end = 0;
int minStart = 0, minEnd = 0;
int minLength = s.length();

bool mark = false; //表示是否有搜索到这样的窗口

text[s[end]]++; //第一个元素加进去
while (end < s.size())
{
if (compare(text, pattern))
{
//找到一个窗口了
int currentLen = end - start + 1;
if (minLength >= currentLen)
{
mark = true;
minLength = currentLen;
minEnd = end;
minStart = start;
}
if (start < end)
{
//在保证start指针是在end指针之前,可以收缩
//否则就要end往右扩展
start++;
text[s[start - 1]]--; //收缩 左边的窗口后移
}
else
{
end++; //严格来说并不会走到这一步
if (end<s.size())
text[s[end]]++; //右边的窗口后移
}

}
else
{
end++; //右边的窗口后移
if (end<s.size())
text[s[end]]++;
}
}
string res;
if (mark)
{
res= s.substr(minStart,minEnd-minStart+1);
return res;
}
else
{
return res;//没有找到返回空
}
}
bool compare(vector<int>text,vector<int>pattern)
{
//大小都是设置的128
int i;
for (i = 0; i < range; i++)
{
if (text[i] < pattern[i])
return false;
}
return true;
}
};



  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017