解题思路:
- 利用Array的index存两个string的词频。
- 什么情况下找到一个valid的字符;
- 什么情况下找到一个valid的完整字符串;
当找到这个字符串的时候:
- 跳过前面多余的字符;
- 更新需求,即最短长度;若更新了,记录开头和结尾;
- 跳过这个字符串的首字符,继续扫(found也要减一)。
====
看到题的第一反应,先数S中每个字母有多少个,以后后面一定要一个一个减掉。
我最初的想法:
s = “DADOBECODEBANC”
t = “ABC“
okay, scan S, start from the letter that also appears in T. here, we start from ADOBEC. this is an possible answer。
Then we skip the first A (cnt A--), start from B, BECODEBA. But when we arrives B, which locates between E and A, we skip the first B (cnt B --), since it will definitely gives shorter answer. keep working till the end.
因为先要存t的字频,之后查表,所以一定会用到hashTable/hashMap;
看了答案,答案用了hash的思想,但是只用array就存储了cnt的信息。
public class Solution {
public String minWindow(String s, String t) {
int[] sCnt = new int[255];
int[] tCnt = new int[255];
for (int i=0; i<t.length(); i++) {
tCnt[t.charAt(i)]++;
}
int start = 0;
int begin = -1, end = s.length();
int found = 0, minLen = s.length();
for (int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
sCnt[c1]++;
if(sCnt[c1] <= tCnt[c1]) found++;
if(found == t.length()) {
while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
sCnt[s.charAt(start)]--;
start++;
}
if(i-start < minLen) {
minLen = i-start;
begin = start;
end = i;
}
sCnt[s.charAt(start)]--;
start++;
found--;
}
}
return begin == -1 ? "" : s.substring(begin, end+1);
}
}
总结一下:直接在代码里写吧。
public class Solution {
public String minWindow(String s, String t) {
int[] sCnt = new int[255];
int[] tCnt = new int[255];
for (int i=0; i<t.length(); i++) {
tCnt[t.charAt(i)]++;
}
int start = 0;
int begin = -1, end = s.length();
int found = 0, minLen = s.length();
for (int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
sCnt[c1]++;
/** 如果算上这个字符后,数量不超过t中这个字符的数量,那么这个字符算是valid(即找到一个匹配的字符);
*/
if(sCnt[c1] <= tCnt[c1]) found++;
/** 找到一个valid的字符串。
*/
if(found == t.length()) {
/** 这个字符串end一定是i。现在需要找到这个字符串的起始位置。
* 起始位置那个字符在s中出现的次数一定和在t中出现的次数一样多;
* 所有那些s中出现次数比t中多的,一定是多余的,从前往后扫,然后全部删掉。
* 记得每次从s中散掉的时候,s对这个字符的cnt也要减一。
*/
while (start<i && sCnt[s.charAt(start)]>tCnt[s.charAt(start)]) {
sCnt[s.charAt(start)]--;
start++;
}
/** 更新minLen,如果更新了,那么记录下这个长度的起始点和终点。
*/
if(i-start < minLen) {
minLen = i-start;
begin = start;
end = i;
}
/** 把开头的start跳过,注意sCnt也要减一,继续扫。
*/
sCnt[s.charAt(start)]--;
start++;
found--;
}
}
return begin == -1 ? "" : s.substring(begin, end+1);
}
}
网友评论