76. Minimum Window Substring

题目描述和难度

  • 题目描述:

给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。

示例:

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

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 ""
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

思路分析

求解关键:使用滑动窗口的思想,并且使用两个字符计数数组。先复习第 438 题再做这题可能会好些,解决它们都用了相同的策略。

  • S 的字符计数数组记录了当前滑动窗口包括的字符的个数,是动态变化的。
  • T 的字符计数数组记录了字符串 T 中的字符的个数,扫描过一次以后这个数组我们不去动它,用来和 S 的字符计数数组进行对应位置上的比较。

参考解答

参考解答1

import java.util.HashSet;
import java.util.Set;

public class Solution {

    public String minWindow(String s, String t) {
        int[] cntS = new int[256];
        int[] cntT = new int[256];

        Set<Character> set = new HashSet<>();
        // cntT 赋值了以后,就成为了用于比对的对象,不更新
        for (char ct : t.toCharArray()) {
            cntT[ct]++;
            set.add(ct);
        }

        int minSub = s.length() + 1;
        String res = "";
        int left = 0;
        int right = 0;
        int count = 0;
        while (right < s.length()) {
            char rc = s.charAt(right);
            if (!set.contains(rc)) {
                // 不在字典里面,但是右边界同样要扩充,所以 right++
                right++;
                continue;
            }
            cntS[rc]++;
            right++;
            // 理解这里是关键:加上以后,小于等于,count 才 ++,
            if (cntS[rc] <= cntT[rc]) {
                // count++; 这件事情说明滑动窗口里面的有效字符,向目标字符又近了一步
                count++;
            }

            // 下面这一段可以写得更精简一些,但是为了语义上的清晰,我就写得冗长一些
            if (count == t.length()) {
                // 接下来,考虑左边界移出滑动窗口
                // 不在字典中,或者多了的时候,直接划掉就可以了
                while (true) {
                    char deleteChar = s.charAt(left);
                    if (!set.contains(deleteChar)) {
                        left++;
                        continue;
                    }
                    if (cntS[deleteChar] > cntT[deleteChar]) {
                        cntS[deleteChar]--;
                        left++;
                        continue;
                    }
                    break;
                }
                if (right - left < minSub) {
                    minSub = right - left;
                    res = s.substring(left, right);
                }
            }
        }
        if (minSub == s.length() + 1) {
            return "";
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0076-minimum-window-substring ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com