剑指 Offer II 017. 含有所有字符的最短字符串

滑动窗口
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)))
        }
        
       
    
    }