Lintcode32 Minimum Window Substring solution 題解

【題目描述】

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Notice:If there is no such window in source that covers all characters in target, return the emtpy string "".If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

給定一個(gè)字符串source和一個(gè)目標(biāo)字符串target，在字符串source中找到包括所有目標(biāo)字符串字母的子串。

注意:如果在source中沒有這樣的子串，返回""，如果有多個(gè)這樣的子串，返回起始位置最小的子串。

【題目鏈接】

http://www.lintcode.com/en/problem/minimum-window-substring/

【題目解析】

可以用窗口型兩個(gè)指針的思路來解決，外層for循環(huán)i = 0 ... n, 內(nèi)層while循環(huán)，條件是j < source.length() 和 !isValid(sourceHash, targetHash)，前者是數(shù)組下標(biāo)邊界，后者是一個(gè)函數(shù)，檢查當(dāng)前窗口中的substring是否包含了目標(biāo)字符串中全部所需的字符，未滿足則繼續(xù)擴(kuò)大窗口j++，同時(shí)更新sourceHash。這里sourceHash，targetHash是整型數(shù)組int[]，因?yàn)锳SCII碼最多256個(gè)，因此用int[]可以作為簡化的HashMap使用，key是char對應(yīng)的int的值，value則是該char在substring中的出現(xiàn)個(gè)數(shù)。isValid函數(shù)則檢查sourceHash是否全部包含了targetHash，256個(gè)字符一一對應(yīng)，因此只需一重for循環(huán)，如果sourceHash[i] < targetHash[i]，則說明有字符未滿足條件。

需要注意的是，要設(shè)定一個(gè)輔助變量記錄minStr的長度。

【參考答案】

http://www.jiuzhang.com/solutions/minimum-window-substring/