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.

給定一個字符串source和一個目標字符串target，在字符串source中找到包括所有目標字符串字母的子串。

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

【題目鏈接】

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

【題目解析】

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

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

【參考答案】

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