最后更新
一刷
08-Jan-2017
昨天Amazon group面结束，刚回家。
国内以前喜欢的女生结婚了，嘿嘿...好开心呀~~
这次面试感觉自己的做法完爆别人，比什么2 greedy好多了= = 总之表现比想象的好，最后一面的面试官真是聪明得一逼，我的思路稍微说她就明白，跪了，这也太出色了。 我只能说A家对于背题党直接OA拿VIDEO或者OFFER确实水，但是有实力的也有，比如给我面试的这个印度姐姐，屌屌屌。
总之希望自己能过能过。
开始准备Google吧。
言归正传。
一长一短2个String
在长的String里找最短的substring，使得substring包含所有短string的字符。
（'a'在短字符串里出现2次，substring里也要出现2次才行）
2 pointers来做的，固定左边，右边往右找，直到substring满足要求。 在往右的过程中，我们可能添加了很多不必要元素：
要满足abc
我们在ab baba cba里找，找到C的时候，添加了baba这段没用的，这个时候尝试左边缩进。
比较通过2个int[256]，一个是需要的字符数，一个是现有的。
Time: O(n)
Space: O(1)
public class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int[] need = new int[256];
int[] count = new int[256];
for (char c : t.toCharArray()) {
need[c]++;
}
int right = 0;
String res = "";
int minLength = Integer.MAX_VALUE;
for (int left = 0; left < s.length(); left++) {
while (right < s.length() && !contains(need, count)) {
count[s.charAt(right++)] ++;
}
if (right - left < minLength && contains(need, count)) {
minLength = right - left;
res = s.substring(left, right);
}
count[s.charAt(left)] --;
}
return res;
}
public boolean contains(int[] need, int[] count) {
for (int i = 0; i < 256; i++) {
if (need[i] > count[i]) {
return false;
}
}
return true;
}
}
方法二：
也是2 pointers，和一的做法差不多，唯一不同的就是判断是否包含的方法。
方法一是通过比较int[256]来判断是否包含所有character，这里有个别的方法。
比如短string是abcde，那么总共需要5个字符才能满足。但也不是随便5个字符就能满足，只有某些字符才能满足。
比如：
一开始是abcde，需要5个才能满足，而a,b,c,d,e其中任何一个都是有效字符。
假如我们substring中已经有了a和c，需要bde，此时的有效字符就变成了b,d,e，读到b,d,e才可以让需要数字++
同理，缩进也要判断，比如substring里有3个A，缩进最左边缩小了1个A，那么当前需要的元素数量是不变的，因为我们还有2个A可以使用，相反如果缩掉了B，而我们substring里没有B了，总共需要的元素数量就要++
if (--chars[s.charAt(right++)] >= 0) {
validRead ++;
}
这个说的是，substring读取一个，然后判断是否是有效读取，把那些-- ++之类的给展开就一目了然了，后面的+ + --一样 ，展开再看。
public class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || s.length() < t.length()) return "";
String res = "";
int minLength = Integer.MAX_VALUE;
int[] chars = new int[256];
for (char c : t.toCharArray()) {
chars[c] ++;
}
int need = t.length();
int validRead = 0;
int right = 0;
for (int left = 0; left < s.length(); left ++) {
while (right < s.length() && validRead < need) {
if (--chars[s.charAt(right++)] >= 0) {
validRead ++;
}
}
if (validRead >= need && right - left < minLength) {
minLength = right - left;
res = s.substring(left, right);
}
if (++chars[s.charAt(left)] > 0) validRead --;
}
return res;
}
}
方法二是因为后面的题要用到这个办法。