[经典面试题][搜狗]在一个字符串中寻找包含全部出现字符的最小字

题目

一个字符串中含有n个字符，，其中有m个不同的字符，n>>m，用最少的时间和空间找到包含所有这m个字符的最短的字串，不考虑特殊字符，只考虑字母数字即可。 例如： abccbaddac, 返回：cbad aabcadbbbcca，返回：bcad

思路

[算法系列之二十二]包含T全部元素的最小子窗口 本题目相比连接中所说的稍微简单一些，本题目不用考虑重复字符。

代码

/*———————————————* 日期：2015-02-24* 作者：SJF0115* 题目: 包含全部出现字符的最小字串* 来源：搜狗* 博客：———————————————–*/;string MinWindow(string S){int slen = S.size();if(slen <= 0){return “”;}//ifint minWinStart,minWinEnd;int minWinLen = INT_MAX;// 统计不同字符个数int m = 0;int needFind[256] = {0};for(int i = 0;i < slen;++i){needFind[S[i]] = 1;}//forfor(int i = 0;i < 256;++i){if(needFind[i] == 1){++m;}//if}//forint hasFound[256] = {0};int val;int count = 0;for(int start = 0,end = 0;end < slen;++end){val = S[end];++hasFound[val];if(hasFound[val] <= 1){++count;}(count == m){int startEle = S[start];while(hasFound[startEle] > 1){–hasFound[startEle];++start;startEle = S[start];}//whileint curWinLen = end – start + 1;if(minWinLen > curWinLen){minWinLen = curWinLen;minWinStart = start;minWinEnd = end;}//if}//if}//forif(count != m){return “”;}//ifreturn S.substr(minWinStart,minWinEnd – minWinStart + 1);}int main() {string S(“aabcadbbbcca”);cout<<MinWindow(S)<<endl;}

引用：

[算法系列之二十二]包含T全部元素的最小子窗口

相似题目：

[LeetCode]76.Minimum Window Substring

人生就像是一场旅行，遇到的既有感人的，