Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S =
"ADOBECODEBANC"
T =
"ABC"
Minimum window is
"BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string
""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
A:
之前根据max-crossing subArray的想法,貌似在计算的cross时候,还是不够efficiency.
是不是,可以根据KMP算法呢???
双指针,动态维护一个区间。尾指针不断往后扫,当扫到有一个窗口包含了所有T的字符后,然后再收缩头指针,直到不能再收缩为止。最后记录所有可能的情况中窗口最小的
------------复杂度呢???? 由于被查找的string最多也就265个字符。因此,可以把其看做是constant的, 那么,复杂度就是O(n)了 -------------------
这道题目,最大的注意之处,就是head 和tail指针的 update 方式。不能处理得太粗糙。
Mistakes:
1: 在find cross 的时候,由于low high是inclusive的,因此在计算长度的时候, 要high-low +1
for (int i = leftStart; i <= rightEnd+1 - curLen; i++) {
2: 题意理解错误。
Input: | "a", "aa" |
Output: | "a" |
Expected: | "" |
3: 认为最后tail会== S.length() 是正确的, 但是,之间,还依然是inclusive的。 所以,不需要把它当做 exclusive来对待。
4: 哎,犯了一个很SB的错误。 在update tail 指针的时候,要对每个位置,检查加上后,是否满足match条件,如果是,则退出来。
但是,原本,就随手写了个while (!allFind(count, times) && tail < S.length()) { 这样,逻辑是比较混乱的。
Learned:
-------------第二遍-----------, T中是有计数的,例如S= "a", T = "aa" ,结果应该是false------
另外,这次,当S超过10000的时候,会有说String index out of 10000的错误。不知道为什么??????????????????????????????????
????????????????
public class Solution { public String minWindow(String S, String T) { if(S==null || T == null) return ""; HashMap<Character, Integer> origMap = new HashMap<Character, Integer>(); HashMap<Character, Integer> findMap = new HashMap<Character, Integer>(); HashMap<Character, Integer> totalMap = new HashMap<Character, Integer>(); int start = 0, minStart = S.length(),minEnd = Integer.MAX_VALUE; for(int i = 0;i<T.length();i++ ){ char ch = T.charAt(i); if(origMap.containsKey(ch)){ origMap.put(ch,origMap.get(ch)+1); }else{ origMap.put(ch,1); } } // if a char in S are find in T, if enough apperarance of char, we put it in findMap, otherwise put in totalMap for(int i =0;i<S.length();i++){ char ch = S.charAt(i); if(origMap.containsKey(ch) == false) continue; int count = origMap.get(ch); if(findMap.containsKey(ch)){ findMap.put(ch,findMap.get(ch)+1); }else{ if(totalMap.containsKey(ch)){ totalMap.put(ch,totalMap.get(ch)+1); }else{ totalMap.put(ch,1); } // check if enough appearance if(totalMap.get(ch)>=origMap.get(ch)){ findMap.put(ch,totalMap.get(ch)); totalMap.remove(ch); } } // check whether we can shrink while(findMap.size()==origMap.size()){// find a match, and begin to shrink char newChar = S.charAt(start); if(origMap.containsKey(newChar)){ if(findMap.get(newChar) == origMap.get(newChar)){ // begin to delete totalMap.put(newChar,findMap.get(newChar)-1); if(minEnd - minStart > i - start){ minStart = start; minEnd = i; } findMap.remove(newChar); }else{ findMap.put(newChar,findMap.get(newChar)-1); } } start++; } } return minStart==S.length()?"":S.substring(minStart,minEnd+1); } }
---------------3 rd Pass -------------不错不错, 方法虽然是新的idea,但是, 只改了几个拼写错误 , 然后,就一遍过了 -------- 哎,Tiger,有进步阿-------------------
IDEA:
用一个HashSet记录是不T 中出现过的字母。 (其实可以用查询MapT,usedMap来代替的,为了清晰,我们这里还是用了)
然后,用一个HashMap, 记录出现字母在T中的次数。 以及发现了的次数。
然后,如果全部发现的话,就把这个对象放进另一个HashMap中缓存起来(当然,如果再次发现的话,也要在这个缓存的Map中更新 nFind。
public class Solution { public String minWindow(String S, String T) { String result = null; // IDEA: use to map to count the strings , if for a char, all are used, // Note that duplicates in T are also counted // build HashMap for T HashMap<Character, Node> mapT = new HashMap<Character, Node>(); HashSet<Character> set = new HashSet<Character>(); HashMap<Character, Node> usedMap = new HashMap<Character, Node>(); for (int i = 0; i < T.length(); i++) { char ch = T.charAt(i); if (mapT.get(ch) == null) { Node tmp = new Node(); mapT.put(ch, tmp); set.add(ch); } else { mapT.get(ch).count++; } } int begin = 0;// begin of current sub window for (int i = 0; i < S.length(); i++) { char ch = S.charAt(i); if (!set.contains(ch)) { // not in the T String continue; } Node tmp = mapT.get(ch); if (tmp == null) {// should be in usedMap, tmp = usedMap.get(ch); tmp.nFind++; } else {// ch appeared in mapT, then we need check tmp.nFind++; if (tmp.count == tmp.nFind) { // all appearance have been found mapT.remove(ch); usedMap.put(ch, tmp); } } // check whether we should shrink, and from beginning while (mapT.isEmpty()) { if (result == null || result.length() > i - begin + 1) { result = S.substring(begin, i + 1); } char tmpChar = S.charAt(begin); begin++; if (set.contains(tmpChar)) { Node tmpNode = usedMap.get(tmpChar); if (tmpNode.nFind == tmpNode.count) { usedMap.remove(tmpChar); mapT.put(tmpChar, tmpNode); } tmpNode.nFind--; } } } return result == null ? "" : result; } } class Node { public int count, nFind;// count if char, and number of find char public Node() { count = 1; nFind = 0; } }
No comments:
Post a Comment