算法：最小覆盖子字符串

算法

发布日期: 2020-05-23

题目：最小覆盖子字符串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

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

说明：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring

分析

这道题我到手的第一想法是用动态规划，但是后来发现，根本没有办法使用动态规划。首先，动态规划的难点在状态转换，而这道题没办法把以遍历的字符串进行状态记录，所以每次只能记录一下已遍历的字符串中是否有符合的字符串和最小长度，然后每次添加字符的时候都要把已遍历的字符串再遍历一次，因为你不确定是否可以变得更短，或者后面的可以组成更短的符合条件的字符串，所以显然可以发现动态规划很难进行下去。那怎么做呢，这里要提到另外一个概念：动态窗口。

顾名思义，我们要用一个窗口来标记字符串，然后通过窗口的平移和伸缩等进行遍历，直到遇到符合条件的字符串并记录。最终得到符合条件的最小字符串。

我们可以使用两个指针来表示窗口的左边界和右边界。每一轮的循环是：

左指针不动，右指针一直往右，直到他们之间包含了字符串T，也就是所求的字符串。
左指针开始右移，去除掉左边无用的元素字符。
最终得到一个符合条件的字符串，并记录下来。

上面三点是一个循环，然后不断重复，直到末尾。然后选择符合条件最短的字符串。

然后还有两个问题：

如何判断该字符是否在所求的字符串t中？如何判断左右指针之间是否已经包含了所求的字符串？这个问题可以通过维护一个hashMap来解决。先遍历一次所求的字符串t并把字符和对应的数目放进hashMap中，之后每遍历一次就-1，如果所有值都<=0则说明已符合要求。

解答

class Solution {
       fun minWindow(s: String, t: String): String {
        if (s.isEmpty()||t.isEmpty()) return ""

        val hashMap  = HashMap<Char,Int>()
        for (char in t){
            if (hashMap.containsKey(char)) hashMap[char] = hashMap[char]!!+1
            else hashMap[char] = 1
        }
        var num = t.length
        var string = ""
        var pointLeft = 0
        var pointRight = 0

        while (pointRight!=s.length){
            while (num!=0 && pointRight<s.length){
                val char = s[pointRight]
                if (hashMap.containsKey(char)){
                    hashMap[char] = hashMap[char]!!-1
                    hashMap[char]?.let {
                        if (it>=0) num--
                    }
                }
                pointRight++
            }

            while (num==0 && pointLeft<pointRight){
                val char = s[pointLeft]
                if (hashMap.containsKey(char)){
                    hashMap[char] = hashMap[char]!!+1
                    if (hashMap[char]!!>0){
                        num++
                        if (string.isEmpty() || string.length>pointRight-pointLeft)
                            string = s.substring(pointLeft,pointRight)
                    }
                }
                pointLeft++
            }

        }
        return string

    }
}