Posts Tagged ‘map’
- 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;
}
给一个String[] L，里面可以有重复，在S里找能包括所有L且都只出现一次的window的start。比如foobarthebarfooman, L={foo, bar}, return 0, 9.
这题正经做了一段时间。
public ArrayList<Integer> findSubstring(String S, String[] L) {
final Map<String, Integer> need = new HashMap<String, Integer>();
for (int i = 0; i < L.length; i++) {
need.put(L[i], need.get(L[i]) == null ? 1 : need.get(L[i]) + 1);
}
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < L[0].length(); i++) {
populateResult(result, S, L, i, need);
}
return result;
}
private void populateResult(ArrayList<Integer> result, String S, String[] L,
int start, final Map<String, Integer> need) {
int k = L[0].length();
HashMap<String, Integer> has = new HashMap<String, Integer>();
for (int end = start; end <= S.length() - k; end += k) {
String sub = S.substring(end, end + k);
if (need.containsKey(sub)) {
while (has.get(sub) == need.get(sub)) {
String tmp = S.substring(start, start + k);
has.put(tmp, has.get(tmp) - 1);
start += k;
}
has.put(sub, has.get(sub) == null ? 1 : has.get(sub) + 1);
if (end - start + k == L.length * L[0].length())
result.add(start);
} else {
has.clear();
start = end + k;
}
}
}
Lexi's Leetcode solutions 