lintcode 32. 最小子串覆盖

ゝ一世哀愁。 2023-07-03 08:16 4阅读 0赞

给定两个字符串 source 和 target. 求 source 中最短的包含 target 中每一个字符的子串.

样例
    样例 1:
    
    输入: source = "abc", target = "ac"
    输出: "abc"
    样例 2:
    
    输入: source = "adobecodebanc", target = "abc"
    输出: "banc"
    解释: "banc" 是 source 的包含 target 的每一个字符的最短的子串.
    样例 3:
    
    输入: source = "abc", target = "aa"
    输出: ""
    解释: 没有子串包含两个 'a'.
    挑战
    O(n) 时间复杂度
    
    注意事项
    如果没有答案, 返回 "".
    保证答案是唯一的.
    target 可能包含重复的字符, 而你的答案需要包含至少相同数量的该字符.

思路：  
1、计算target各字符出现次数  
2、遍历source数组，如果出现target中相同字符，且目前出现次数不多于target，则found++  
3、found与target长度相同，说明该字段拥有了target所有字符  
4、将该字段的字符从前面开始删除，直到拥有target字符的最小长度  
5、与已找出的符合要求最小长度比较，若小，则替换起始点等数据  
6、以此类推，继续循环

class Solution {
        
    public:
        /**
         * @param source : A string
         * @param target: A string
         * @return: A string denote the minimum window, return "" if there is no such a string
         */
        string minWindow(string &source , string &target) {
        
            // write your code here
            if(target.size()==0||source.size()==0) return "";
            int scount[128]={
        0},tcount[128]={
        0};
           /* for (int i = 0; i < 128; i++) {
                scount[i]=0;
                tcount[i]=0;
            }*/
            for (int i = 0; i < target.size(); i++) {
        
                tcount[target[i]]++;
            }
            int begin=-1;
            int start=0;
            int minlen=source.size();
            int found=0;
            int end=source.size()-1;
            for (int i = 0; i < source.size(); i++) {
        
                scount[source[i]]++;
                if(scount[source[i]]<=tcount[source[i]]) found++;
                if(found==target.size())
                {
        
                    while(start<=i&&scount[source[start]]>tcount[source[start]])
                    {
        
                        scount[source[start]]--;
                        start++;
                    }
                    if(i-start+1<=minlen)
                    {
        
                        begin=start;
                        end=i;
                        minlen=i-start+1;
                    }
                    scount[source[start]]--;
                    start++;
                    found--;
                }
            }   
            if(begin==-1) return"";
            return source.substr(begin,minlen);
        }
    };