程序员

lintcode 第三十二题 最小子串覆盖

给定一个字符串source和一个目标字符串target,在字符串source中找到包括所有目标字符串字母的子串。
注意事项
如果在source中没有这样的子串,返回””,如果有多个这样的子串,返回起始位置最小的子串。
说明
在答案的子串中的字母在目标字符串中是否需要具有相同的顺序?
——不需要。
样例
给出source = “ADOBECODEBANC”,target = “ABC” 满足要求的解 “BANC”
这道题其实是让我们找到包含target所有字母的最小子串,题目要求时间为O(n),我么使用哈希表。
首先建一个map(我并没有使用C++里面的map,而是用的vector,道理是一样的),大小分配128(所有大写字母的ASCII码不超过128),初始化为0。遍历target,是map相应的位置上加1。之后设置两个指针,begin和end,用于计算长度。当target的字母在source中出现时,counter减1,当counter减为0时,target中的全部字母已包含在source的子串中,接着我们比较子串的长度选出最小的即可。
代码如下:

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
        vector map(128,0);
        for (auto c : target) map[c]++;
        int counter = target.size(),begin = 0,end = 0,d = INT_MAX,head = 0;
        while (end < source.size()) {
            if (map[source[end++]]-- > 0) counter--;
            while (counter == 0) {
                if (end - begin < d) {
                    d = end - begin;
                    head = begin;
                }
                if (map[source[begin++]]++ == 0) counter++;
            }
        }
        return d == INT_MAX ? "" : source.substr(head,d);
    }
};