滑动窗口
1、如果t的长度为0 或者 s的长度比t的短 不符合条件
2、创建needDict遍历字符串t 记录字符出现的次数。key为字符 value为出现次数
3、创建matchDict记录s中的字符 开始遍历字符串s
如果需要的字典needDict中含有这个字符 就在 matchDict中记录
vaild变量用来记录 是否所有的字符数量符合要求
当数量和需要的字典中相同的时候 说明找到合适的字符串了
记录下开始位置start和长度length，最后返回的时候使用
4、当符合要求的时候 开始移动左指针收紧窗口 寻找最优解
左指针移动 直到移动到需要的字符时 减去所需字符的数量 右指针继续移动 寻找下一个位置
ps：这种的效率不是很高= =。。但是题目中含有大小写字母 用数组的话 要创建一个56长度的= =
要是还含有别的字符呢。。 相对的 这种方法又算是比较好的 不用去考虑字符ASCII码的值
func minWindow(_ s: String, _ t: String) -> String {
if t.count == 0 || s.count < t.count {
return ""
}
var needDict = Dictionary<Character,Int>()
var matchDict = Dictionary<Character,Int>()
for c in t {
if let count = needDict[c] {
needDict[c] = count + 1
} else {
needDict[c] = 1
}
}
//swift字符串没有下标方法 转下数组
let array = Array(s)
var left = 0
var right = 0
var vaild = 0 //用来判断是否达到条件
var start = 0
var length = Int.max //用来记录长度
for c in s {
if needDict[c] != nil {
if let count = matchDict[c] {
matchDict[c] = count + 1
} else {
matchDict[c] = 1
}
//数量达到要求了
if matchDict[c] == needDict[c] {
vaild += 1
}
}
right += 1
//如果全部达到条件了
while needDict.count == vaild {
//更新长度
if right - left < length {
start = left
length = min(length, right - left)
}
let d = array[left]
left += 1
//开始移动左边界
if needDict[d] != nil {
if matchDict[d] == needDict[d] {
vaild -= 1
}
if let count = matchDict[d] {
matchDict[d] = count - 1
}
}
}
}
if length == Int.max {
return ""
}
else{
let ret = s as NSString
return String(ret.substring(with: NSMakeRange(start, length)))
}
}
网友评论