32. 最小子串覆盖

描述

给定一个字符串 source 和一个目标字符串 target，在字符串 source 中找到包括所有目标字符串字母的子串。
如果在 source 中没有这样的子串，返回""，如果有多个这样的子串，返回起始位置最小的子串(长度最短的子串)。

说明

在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？
——不需要。

样例

给出source ="ADOBECODEBANC"，target ="ABC" 满足要求的解 "BANC"

挑战

要求时间复杂度为O(n)

思路

利用 hash 表来记录字符串中字母出现次数
当 target 中每个字母在 sourcehash 表中出现次数大于在 targethash 表中出现次数则认为满足包含条件

注

字符串ABCD 和子串 EF 检查子串是否在字符串中，如果用两个for循环暴力解法，最外层先遍历子串，子串每一个字母都在字符串中进行查找

代码

public class Solution {    
    int initTargetHash(int []targethash, String Target) {
        int targetnum =0 ;
        for (char ch : Target.toCharArray()) {
            targetnum++;
            targethash[ch]++;
        }
        return targetnum;
    }
    
    boolean valid(int[] sourcehash, int[] targethash) {
        for (int i = 0; i < 256; i++) {
            if (targethash[i] > sourcehash[i]) {   
                return false;
            }
        }
        return true;
    }
    
    public String minWindow(String Source, String Target) {
        int ans = Integer.MAX_VALUE;
        String minStr = "";
        
        int[] sourcehash = new int[256];
        int[] targethash = new int[256];
        
        initTargetHash(targethash, Target);
        // i j 分别是子串在字符串中的起始位置
        int j = 0, i = 0;
        for (i = 0; i < Source.length(); i++) {
            while (!valid(sourcehash, targethash) && j < Source.length()) {
                sourcehash[Source.charAt(j)]++;
                // j 位置的字母在 hash 表中次数加1后 j++
                j++;
            }
            if (valid(sourcehash, targethash)) {
                if (ans > j - i) {
                    ans = Math.min(ans, j - i);
                    // minStr不包含 j
                    minStr = Source.substring(i, j);
                }
            }
            sourcehash[Source.charAt(i)]--;
        }
        return minStr;
    }
}