原文链接: https://leetcode-cn.com/problems/M1oyTv

中文题目

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

 

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

 

示例 1：

复制

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

复制

输入：s = "a", t = "a"
输出："a"

示例 3：

复制

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

 

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

 

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

 

注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-substring/

通过代码

高赞题解

思路和心得：

1.滑动窗口+临界统计

2.记录好每次符合条件的起始点和长度即可

复制

[]
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        sn = len(s)
        tn = len(t)
        
        res_start = -1
        res_len = float('inf')

        need_cnt = tn
        need_char_cnt = defaultdict(int)
        for c in t:
            need_char_cnt[c] += 1

        l = 0
        for r in range(sn):
            if s[r] in need_char_cnt:
                if need_char_cnt[s[r]] > 0:
                    need_cnt -= 1
                need_char_cnt[s[r]] -= 1
            if need_cnt == 0:
                while True: 
                    if s[l] not in need_char_cnt:
                        l += 1
                    else:
                        if need_char_cnt[s[l]] < 0:
                            need_char_cnt[s[l]] += 1
                            l += 1
                        else:
                            break
                cur_len = r - l + 1
                if cur_len < res_len:
                    res_len = cur_len
                    res_start = l
        if res_start != -1:
            return s[res_start: res_start + res_len]
        return ""

复制

[]
class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int sn = s.size();
        int tn = t.size();

        if (sn < tn)
            return string("");

        int need_cnt = tn;
        unordered_map<char, int> need_char_cnt;
        for (char c : t)
            need_char_cnt[c] ++;
        
        int res_start = -1;
        int res_len = INT_MAX;

        int l = 0;
        for (int r = 0; r < sn; r ++)
        {
            if (need_char_cnt.find(s[r]) != need_char_cnt.end())
            {
                if (need_char_cnt[s[r]] > 0)
                    need_cnt --;
                need_char_cnt[s[r]] --;
            }

            if (need_cnt == 0)
            {
                while (true)
                {
                    if (need_char_cnt.find(s[l]) == need_char_cnt.end())
                        l ++;
                    else
                    {
                        if (need_char_cnt[s[l]] < 0)
                        {
                            need_char_cnt[s[l]] ++;
                            l ++;
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                if (r - l + 1 < res_len)
                {
                    res_len = r - l + 1;
                    res_start = l;
                }
            }
        }

        if (res_start == -1)
            return string("");
        return s.substr(res_start, res_len);
    }
};

复制

[]
class Solution 
{
    public String minWindow(String s, String t) 
    {
        int sn = s.length();
        int tn = t.length();

        if (sn < tn)
            return new String();
        
        int need_cnt = tn;
        Map<Character, Integer> need_char_cnt = new HashMap<>();
        for (int i = 0; i < tn; i ++)
        {
            char c = t.charAt(i);
            need_char_cnt.put(c, need_char_cnt.getOrDefault(c, 0) + 1);
        }

        int res_start = -1;
        int res_len = Integer.MAX_VALUE;
        
        int l = 0;
        for (int r = 0; r < sn; r ++)
        {
            if (need_char_cnt.containsKey(s.charAt(r)) == true)
            {
                if (need_char_cnt.get(s.charAt(r)) > 0)
                    need_cnt --;
                need_char_cnt.put(s.charAt(r), need_char_cnt.get(s.charAt(r)) - 1);
            }

            if (need_cnt == 0)
            {
                while (true)
                {
                    if (need_char_cnt.containsKey(s.charAt(l)) == false)
                        l ++;
                    else
                    {
                        if (need_char_cnt.get(s.charAt(l)) < 0)
                        {
                            need_char_cnt.put(s.charAt(l), need_char_cnt.get(s.charAt(l)) + 1);
                            l ++;
                        }
                        else
                        {
                            break;
                        }
                    }
                }

                if (r - l + 1 < res_len)
                {
                    res_len = r - l + 1;
                    res_start = l;
                }
            }
        }

        if (res_start == -1)
            return new String();
        return s.substring(res_start, res_start + res_len);
    }
}

统计信息

通过次数	提交次数	AC比率
4438	8637	51.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言