打卡-最小覆盖子串
2020-05-23 本文已影响0人
A邱凌
最小覆盖子串(困难)
class MinWindow {
/*
* 76. 最小覆盖子串
* 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
* 示例:
* 输入: S = "ADOBECODEBANC", T = "ABC"
* 输出: "BANC"
* 说明:
* 如果 S 中不存这样的子串,则返回空字符串 ""。
* 如果 S 中存在这样的子串,我们保证它是唯一的答案。
* */
/*
* 明显滑动窗口问题 思考:什么时候应该使用滑动窗口?
* 当我们需要找出最小区间 并且向右扩张没有意义 左边扩张解决最优解
* */
fun minWindow(s: String, t: String): String {
if (t.isEmpty() || s.isEmpty()) {
return ""
}
var needs: MutableMap<Char, Int> = mutableMapOf()
var windows: MutableMap<Char, Int> = mutableMapOf()
for (i in t) {
needs.put(i, needs[i]?.plus(1) ?: 1)
}
var left = 0
var right = 0
var valid = 0
var start = 0
var len = Int.MAX_VALUE
while (right < s.length) {
var key = s[right]
right++
windows.put(key, windows[key]?.plus(1) ?: 1)
if (windows[key] ?: 0 == needs[key] ?: 0) {
valid++
}
while (valid == needs.size) {
//左指针右移
var key = s[left]
if (right - left < len) {
start = left
len = right - left
}
left++
windows.put(key, windows[key]!!.minus(1))
if (windows[key] ?: 0 < needs[key] ?: 0) {
valid--
}
}
}
return if (len == Int.MAX_VALUE) "" else s.substring(start, start + len)
}
}
fun main() {
println(MinWindow().minWindow("ADOBECODEBANC", "ABC"))
}