LeetCode 76 最小覆盖子串

Ciel Yang 收录于类别练习 OJ解题报告

2020-06-08 2020-06-08 约 859 字预计阅读 2 分钟

本体是一道考察双指针的经典例题，非常值得深入研究和经常复习。

题目描述

原题链接如下： LeetCode 76 最小覆盖子串

题目大意

要在字符串 S 中找到包含 T 的所有字符的最短子串，同时注意 S 和 T 的字符都有可能重复。另外，子串的字符不必和 T 的字符顺序一致。

输入与输出

示例输入为：

1
2
3
Input:
S = "ADOBECODEBANC"
T = "ABC"

对应输出为：

1
2
Output:
"BANC"

解题思路

遇到子串、子数组等问题一般会使用同向双指针构造滑动窗口来求解。在本题中，我们通过在 S 上的滑动窗口能够得到一个不断变化的子串，如果子串的字符不包含 T 的全部字符则子串需要扩张，如果包含则需要收缩。每次收缩之前，都将得到一个包含 T 的所有字符的子串的长度，取它们的最小值就是本题答案。另外，因为字符串比较中的一个字符串 T 是不变的，为了提高比较效率，可以使用计数桶编码 T 的所有字符。这样，在扩张时直接把新添加的子串字符对应的计数减一即可，收缩时则需要把减去的字符对应的计数加一。至于子串是否包含 T 则不必通过统计计数桶是否全部不大于 0，而是通过维护一个匹配长度计数器来实现。在子串扩张时，如果新添加字符对应的计数减一后不小于 0，则表明又找到一个匹配对，匹配计数器加一；在收缩时，如果减少的字符对应的计数加一后大于 0，表明失去一个匹配对，匹配计数器减一。这样，只要匹配计数器等于 T 的长度就表明子串包含 T 的所有字符，即需要收缩。

注意：匹配计数器的值不会超过 T 的长度，因为如果子串中有更多的对应字符，其实就代表了字符对应的计数桶小于 0，此时匹配计数器不会有任何改变。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    fun minWindow(s: String, t: String): String {
        if (s.isEmpty() || t.isEmpty() || s.length < t.length) return ""
        val charTable = IntArray(128)
        t.forEach { charTable[it.toInt()]++ }

        var left = 0
        var right = 0

        var start = 0
        var end = 0
        var minLen = s.length + 1
        var matchCount = 0
        while (right < s.length) {
            val r = s[right].toInt()
            charTable[r]--
            if (charTable[r] >= 0) matchCount++
            right++

            while (matchCount == t.length) {
                if (minLen > right - left) {
                    minLen = right - left
                    start = left
                    end = right
                }
                val l = s[left].toInt()
                charTable[l]++
                if (charTable[l] > 0) matchCount--
                left++
            }
        }
        return s.substring(start, end)
    }
}

本段代码中，虽然有两个嵌套的循环，但是要注意到这两个循环分别代表了子串的扩张和收缩，而不论是扩张还是收缩，最差情况都只会遍历一次 S 的所有字符，因而寻找子串的时间复杂度只有 O(|s|) 而已。

目录

LeetCode 76 最小覆盖子串

题目描述

题目大意

输入与输出

解题思路

代码