leetcode76 最小覆盖字串问题

这是之前刷题时遇到到的一眼懵问题，就是看完第一眼整个人都是懵的，不知道在问什么。所以就习惯性的加到了待办事项中，想来已数月有余，这两天在清理待办事项列表，今天就轮到它了。

题目

原地址

原题是这样的,给一个字符串s，一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有的字符的子串，则返回空字符串“”。

分析

我自己本身是没有思路的，后来查了网上的解析，简单说就一句话，使用双指针，都从左侧开始，指针区间不满足条件时，右移r，当满足条件时右移l，并记录每次的子串，保存最小子串。

做法不难理解，困难的是要具有这种动态处理问题的思想。

首先，子串必连续，s中每个字符作为子串的开头时，要么不存在目标子串，要么仅存在一个最短的目标子串，原因是，当其符合条件时，再向右扩张，则不是最短的了。当以某个字符开头的所有子串中，不存在符合条件的，那么，其右侧的字符作为开头的子串中，也不会存在符合条件的，原因是，右侧字符开头的字符串是该字符开头的字符串的子集，超集不存在符合条件的字符串，那么子集必然不会存在。

两个指针的移动规则确定了，那么接下来的问题就是，如何对比两个指针之间的子串是否满足目标字符串，最直接的方法就是每次更新完指针的位置后，统计出区间的字符数量，然后再和目标字符串的字符数量，循环一一对比看是否可以覆盖。但是，我们可以容易的发现，在每次移动完指针之后，指针之间字符的变化只有指针所指向的字符，左指针右移动，减少一个对应字符数量，右指针右移，增加一个对应字符的数量，所以，就不必每次都重新计算区间情况，而是做一个缓存，每次只更新必要的字符计数。

代码

代码中写了较为详尽的说明

import kotlin.collections.HashMap
import kotlin.math.max

fun minSubStr(s: String, t: String): String {
    if (s.length < t.length || s.isEmpty()) return ""

    var subStart = 0
    var subLength = s.length + 1

    // 记录t的每个字符的数量
    // 统计sub时，只统计t中有的字符
    // 不满足右移r时，可能需要增加计数
    // 满足右移l时，可能需要减少计数
    // 每次移动后，对比t的字符统计和sub的字符统计

    val tDict = HashMap<Char, Int>()
    for (i in t.indices) {
        increment(tDict, t[i])
    }

    var left = 0
    var right = 0
    // 两个指针都指0，所以要先把0加进去
    val subDict = HashMap<Char, Int>().apply { put(s[0], 1) }

    while (left < s.length && right < s.length) {
        val ok = compare(subDict, tDict)
        if (!ok) {
            right++
            if (right < s.length) {
                increment(subDict, s[right])
            }
        } else {
            val interval = right - left
            if (interval < subLength) {
                subStart = left
                subLength = interval
            }
            decrement(subDict, s[left])
            left++
        }
    }

    return if (subLength <= s.length) s.substring(subStart, subStart + subLength + 1) else ""
}

下面是3个辅助方法，很简单，便不多言

// 加1
fun increment(d: HashMap<Char, Int>, k: Char) {
    if (d.containsKey(k)) {
        d[k] = d[k]!! + 1
    } else {
        d[k] = 1
    }
}

// 减1，最小是0
fun decrement(d: HashMap<Char, Int>, k: Char) {
    if (d.containsKey(k)) {
        d[k] = max(0, d[k]!! - 1)
    }
}

// src里的字符数量，是否可以覆盖target里的字符数量
fun compare(src: HashMap<Char, Int>, target: HashMap<Char, Int>): Boolean {
    for (key in target.keys) {
        if (!src.containsKey(key)) return false
        if (src[key]!! < target[key]!!) return false
    }
    return true
}

测试用例是从题目里找来的，一共有3个

fun main() {
    println("hello leetcode 76")

    val s1 = "ADOBECODEBANC"
    val t1 = "ABC"
    println("s:$s1, t:$t1, sub:${minSubStr(s1, t1)}")

    val s2 = "a"
    val t2 = "a"
    println("s:$s2, t:$t2, sub:${minSubStr(s2, t2)}")

    val s3 = "a"
    val t3 = "aa"
    println("s:$s3, t:$t3, sub:${minSubStr(s3, t3)}")
}

// 运行结果
s:ADOBECODEBANC, t:ABC, sub:BANC
s:a, t:a, sub:a
s:a, t:aa, sub: