[leetcode] Minimum Window Substring
Posted November 18, 2013
on:- In: leetcode
- 2 Comments
还是两个map,一个want, 一个has,i指当前window的开头,j指结尾;want满足了的时候就试试能不能从i处删点什么。写了25分钟然后各种debugger,这题还得重做。
public String minWindow(String S, String T) { Map<Character, Integer> has = new HashMap<Character, Integer>(); Map<Character, Integer> want = new HashMap<Character, Integer>(); String res = S + S; char[] s = S.toCharArray(); char[] t = T.toCharArray(); for (int i = 0; i < t.length; i++) { want.put(t[i], want.get(t[i]) == null ? 1 : want.get(t[i]) + 1); has.put(t[i], 0); } int i = 0; for (int j = i; j < s.length; j++) { if (want.containsKey(s[j])) { has.put(s[j], has.get(s[j]) + 1); if (satisfy(has, want)) {// satisfies everything nows, try move i while (!want.containsKey(s[i]) || has.get(s[i]) > want.get(s[i])) { //move i until not movable if (want.containsKey(s[i]) && has.get(s[i]) > want.get(s[i])) has.put(s[i], has.get(s[i]) - 1); i++; } String currWindow = S.substring(i, j + 1); res = res.length() > currWindow.length() ? currWindow : res; } } } return res.length() > S.length() ? "" : res; } private boolean satisfy( Map<Character, Integer> has, Map<Character, Integer> want) { for (Character c : want.keySet()) { if (has.get(c) < want.get(c)) return false; } return true; }
2 Responses to "[leetcode] Minimum Window Substring"

谢谢分享。两个小改进
一个是
for (int j = i; j < s.length; j++) {
j = i有一点confusing,个人觉得j=0比较好,
第二个是 每次satisfy后,advance pointer i 并且decrease has map。 这个改进把running time 从1300ms降到400ms。

August 14, 2014 at 9:50 am
谢谢分享。有一个小的改进,Satisfy成功了一次以后,之后每一次被调用都必定是返回true,所以可以用一个flag来表示是否已经satisfy了,如果是就不用检查want中的每一个字符了。