含有所有字符的最短字符串

剑指 Offer II 017. 含有所有字符的最短字符串

给定两个字符串 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 <= 10⁵
s 和 t 由英文字母组成

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

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: string minWindow(string s, string t) { } };

java 解法, 执行用时: 10 ms, 内存消耗: 42.4 MB, 提交时间: 2023-04-22 12:12:42

class Solution {
    public String minWindow(String source, String target) {
        char[] s = source.toCharArray();
        char[] t = target.toCharArray();

        // needs是需要的字符和数量，window记录窗口中有效的字符和数量
        HashMap<Character, Integer> needs = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        // valid 变量表示窗口中满足 need 条件的字符个数
        int valid = 0;
        int left = 0, right = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;

        for(char c : t){
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }

        while(right < s.length){
            // c 是将移入窗口的字符
            char c = s[right];
            // 扩大窗口
            right++;
            // 进行窗口内数据的一系列更新
            if(needs.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);

                // ⭐注意：两个Integer类型的数据不能直接用< == >判断
                if(window.get(c).equals(needs.get(c))){
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(valid == needs.size()){
                // 在这里更新最小覆盖子串(更新最终结果)
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                // d 是将移要出窗口的字符
                char d = s[left];
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(needs.containsKey(d)){
                    window.put(d, window.get(d) - 1);
                    // window窗口内的数据无法满足，不再有效
                    // ⭐注意：两个Integer类型的数据不能直接用< == >判断
                    if(window.get(d) < Integer.valueOf(needs.get(d))){
                        valid--;
                    }
                }
            }
        }

        // 返回最小覆盖子串(使用三目运算使代码简洁)
        return len == Integer.MAX_VALUE ? "" : source.substring(start, start + len);
    }
}

python3 解法, 执行用时: 68 ms, 内存消耗: 15.4 MB, 提交时间: 2023-04-22 12:11:57

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

golang 解法, 执行用时: 148 ms, 内存消耗: 2.8 MB, 提交时间: 2023-04-22 12:11:14

func minWindow(s string, t string) string {
    ori, cnt := map[byte]int{}, map[byte]int{}
    for i := 0; i < len(t); i++ {
        ori[t[i]]++
    }

    sLen := len(s)
    len := math.MaxInt32
    ansL, ansR := -1, -1

    check := func() bool {
        for k, v := range ori {
            if cnt[k] < v {
                return false
            }
        }
        return true
    }
    for l, r := 0, 0; r < sLen; r++ {
        if r < sLen && ori[s[r]] > 0 {
            cnt[s[r]]++
        }
        for check() && l <= r {
            if (r - l + 1 < len) {
                len = r - l + 1
                ansL, ansR = l, l + len
            }
            if _, ok := ori[s[l]]; ok {
                cnt[s[l]] -= 1
            }
            l++
        }
    }
    if ansL == -1 {
        return ""
    }
    return s[ansL:ansR]
}

java 解法, 执行用时: 95 ms, 内存消耗: 42.3 MB, 提交时间: 2023-04-22 12:10:51

class Solution {
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }
}

上一题

下一题

详情