Blog

leetcode76最小覆盖子串

leetcode76 Minimum Window Substring

Posted by BY on May 9, 2019

前言

新的一年，好好学习。

正文

问题来源

本问题来自leetcode上的76题。

问题描述

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
如果 S 中不存这样的子串，则返回空字符串 ““。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

示例 2：

输入: S = "AA", T = "AA"
输出: "AA"

分析：

说实话我并没有想到好的解决办法，第一反应就是暴力求解，如下是我采用回溯法的解法，很遗憾的是超时了。

func minWindow(s string, t string) string {
    if len(s) < len(t) {
        return ""
    }
    m := make(map[byte]int)
    c := 0
    for i := 0; i < len(t); i++ {
        if _, ok := m[t[i]]; !ok {
            m[t[i]] = c
            c++
        }
    }
    count := make([]int, len(m))
    for i := 0; i < len(s); i++ {
        if index, ok := m[s[i]]; ok {
            count[index]++
        }
    }
    tcount := make([]int, len(m)) 
    for i := 0; i < len(t); i++ {
        tcount[m[t[i]]]++
    }
    if !isContinue(count, tcount) {
        return ""
    }
    return dfs(m, count, tcount, s, 0, len(s)-1)
}

func isContinue(count, tcount []int) bool {
    for i := 0; i < len(count); i++ {
        if count[i] < tcount[i] {
            return false
        }
    }
    return true
}

func dfs(m map[byte]int, count, tcount []int, s string, start, end int) string {
    if !isContinue(count, tcount) {
        return ""
    }
    
    index, ok := m[s[start]]
    if ok {
        count[index]--
    }
    t1 := dfs(m, count, tcount, s, start+1, end)
    if t1 == "" {
        t1 = s[start:end+1]
    }
    if ok {
        count[index]++
    }
    
    index, ok = m[s[end]]
    if ok {
        count[index]--
    }
    t2 := dfs(m, count, tcount, s, start, end-1)
    if t2 == "" {
        t2 = s[start:end+1]
    }
    if ok {
        count[index]++
    }
    if len(t1) > len(t2) {
        return t2
    } 
    return t1
}

这道题和去年做的leetcode 3的思想是类似的，可以重新复习一下
参考网上的代码
思路：思路很简单，就是遍历数组，先把所有的Ｔ中的字符找到，然后从左端缩减这个字符串，直到不能完全包含Ｔ．但是实现起来还是需要一些技巧．因为时间复杂度限制在了O(n)，所以需要在O(1)的时间内判断是不是找到了所有的Ｔ中的字符．可以用一个hash表来计数所有字符出现的次数和一个标记num代表Ｔ总共有多少字符．
然后遍历S，并且将当前字符在hash表中计数减一，如果当前字符在hash表中计数是大于０的，说明这个字符是出现在Ｔ中的，将num也减一，代表我们找到了一个（这个num就是总共有多少字符，我们需要这个来标记是不是找完了所有字符，这也是能够在O(1)时间内判断当前窗口是不是覆盖了Ｔ的关键）．这样当总的数量为０的时候我们就找到了一个覆盖Ｔ的子串窗口．这个窗口因为左端可能包含了一些不必要的字符，因此我们需要将窗口的左端向右移动，使其正好包含Ｔ．在窗口左端向右移动的过程中需要将碰到字符在hash表中＋１，如果当前字符在hash表中的计数为０，而且我们又碰到了，说明这个字符是出现在Ｔ中的，因此num要加一．

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash;
        int num = t.size(), len=INT_MAX, start =0, left = 0;
        for(auto val: t) hash[val]++;
        for(int i =0; i < s.size(); i++)
        {
            if(hash[s[i]]-- >0) num--;
            while(num ==0)
            {
                len = (i-left+1)<len?(i-(start=left)+1):len;
                if(hash[s[left++]]++ ==0) num++;
            }
        }
        return len==INT_MAX?"":s.substr(start, len);
    }
};

然后给出自己golang的实现版本

func minWindow(s string, t string) string {
    if len(s) < len(t) {
        return ""
    }
    m := make(map[byte]int)
    cnt := len(t)
    min := math.MaxInt32
    start, left := 0, 0
    for i := 0; i < cnt; i++ {
        m[t[i]]++
    }
    for i :=0; i < len(s); i++ {
        if m[s[i]] > 0 {
            cnt--
        }
        m[s[i]]--
        for cnt == 0 {
            if min > i - left + 1 {
                min = i - left + 1
                start = left
            }
            if m[s[left]] == 0 {
                cnt++
            }
            m[s[left]]++
            left++
        }
    }
    if min == math.MaxInt32 {
        return ""
    }
    return s[start:start+min]
}

要注意的是golang不能像c++一样采用 if m[s[i]]– > 0 这样的写法，必须将这样的写法进行分解。拆解为 if m[s[i]] > 0 和 m[s[i]]–；golang没有前置++操作；golang没有 (judgement) ? (statement) : (statement) 的三目运算

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog