Shulou(Shulou.com)06/01 Report--

[topic description]

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.

Given a string source and a target string target, find a substring in the string source that includes all the target string letters.

Note: if there is no such substring in source, return "". If there is more than one such substring, return the substring with the smallest starting position.

[topic link]

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

[topic Analysis]

Can be solved with window-type two pointers, the outer for loop I = 0. N, inner while loop, if j < source.length () and! isValid (sourceHash, targetHash), the former is the array subscript boundary, and the latter is a function to check whether the substring in the current window contains all the required characters in the target string, and if it is not satisfied, continue to expand the window, and update sourceHash at the same time. Here sourceHash,targetHash is an integer array int [], because there are up to 256ASCII codes, so int [] can be used as a simplified HashMap, where key is the value of the int corresponding to char, and value is the number of char appearing in the substring. The isValid function checks whether sourceHash contains an one-to-one correspondence of targetHash,256 characters, so it only needs a double for loop. If sourceHash [I] < targetHash [I], it means that some characters do not meet the condition.

It is important to note that an auxiliary variable is set to record the length of the minStr.

[reference answer]

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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.