描述

給定一個(gè)字符串 source 和一個(gè)目標(biāo)字符串 target，在字符串 source 中找到包括所有目標(biāo)字符串字母的子串。
如果在 source 中沒有這樣的子串，返回""，如果有多個(gè)這樣的子串，返回起始位置最小的子串(長(zhǎng)度最短的子串)。

說明

在答案的子串中的字母在目標(biāo)字符串中是否需要具有相同的順序？
——不需要。

樣例

給出source ="ADOBECODEBANC"，target ="ABC" 滿足要求的解 "BANC"

挑戰(zhàn)

要求時(shí)間復(fù)雜度為O(n)

思路

利用 hash 表來(lái)記錄字符串中字母出現(xiàn)次數(shù)
當(dāng) target 中每個(gè)字母在 sourcehash 表中出現(xiàn)次數(shù)大于在 targethash 表中出現(xiàn)次數(shù)則認(rèn)為滿足包含條件

注

字符串ABCD 和子串 EF 檢查子串是否在字符串中，如果用兩個(gè)for循環(huán)暴力解法，最外層先遍歷子串，子串每一個(gè)字母都在字符串中進(jìn)行查找

代碼

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 表中次數(shù)加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;
    }
}