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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
- Method 1:双指针 TLE
class Solution {
public String minWindow(String s, String t) {
if(s == null || t == null) return "";
int min = Integer.MAX_VALUE;
String result = "";
int sLen = s.length();
int tLen = t.length();
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
Map<Character, Integer> cmp = new HashMap<>();
for(int i = 0; i < tLen; i++)
cmp.put(tArr[i], cmp.containsKey(tArr[i]) ? cmp.get(tArr[i]) + 1: 1);
for(int i = 0; i <= sLen - tLen; i++){
if(!cmp.containsKey(sArr[i])) continue;
Map<Character, Integer> temp = new HashMap<>();
temp.put(sArr[i], 1);
if(check(temp, cmp)){
result = s.substring(i, i + 1);
min = 1;
return result;
}
for(int j = i + 1; j < sLen; j++){
if(!cmp.containsKey(sArr[j])) continue;
temp.put(sArr[j], temp.containsKey(sArr[j])?temp.get(sArr[j]) + 1: 1);
if(check(temp, cmp)){
if(j - i + 1 < min){
min = j - i + 1;
result = s.substring(i, j + 1);
}
break;
}
}
}
return result;
}
private static boolean check(Map<Character, Integer> sMap, Map<Character, Integer> tMap){
Set<Character> set = tMap.keySet();
for(Character c : set){
if(!sMap.containsKey(c)) return false;
else
if(sMap.get(c) < tMap.get(c)) return false;
}
return true;
}
}- Method 2: 滑动窗口
class Solution {
public String minWindow(String s, String t) {
if(s == null || t == null) return "";
int[] sMap = new int[256];
int[] tMap = new int[256];
int sLen = s.length();
int tLen = t.length();
for(int i = 0; i < tLen; i++)
tMap[t.charAt(i)]++;
int right = 0;
String result = "";
int min = Integer.MAX_VALUE;
for(int i = 0; i <= sLen - tLen; i++){
while(right < sLen && !check(sMap, tMap)){
sMap[s.charAt(right)]++;
right++;
}
if(check(sMap, tMap) && min > right - i + 1){
min = right - i + 1;
result = s.substring(i, right);
}
sMap[s.charAt(i)]--;
}
return result;
}
private boolean check(int[] sMap, int[] tMap){
for(int i = 0; i < sMap.length; i++){
if(tMap[i] > sMap[i])
return false;
}
return true;
}
}这道题还是借鉴了一刷时候的结果，我先写出来了双指针的方法，最后一个test case无法通过。所以换成了滑动窗口的解法，最后AC。
class Solution {
public String minWindow(String s, String t) {
if(s == null || t == null) return "";
String result = "";
int res = s.length() + 1;
int[] tMap = new int[128];
char[] sArr = s.toCharArray();
char[] tArr = t.toCharArray();
for(int i = 0; i < tArr.length; i++)
tMap[tArr[i]]++;
int[] cmp = new int[128];
int right = 0;
for(int i = 0; i <= sArr.length - tArr.length; i++){
while(right < sArr.length && !same(tMap, cmp)){
cmp[sArr[right++]]++;
}
if(same(tMap, cmp) && right - i + 1 <= res){
res = right - i + 1;
result = s.substring(i, right);
}
cmp[sArr[i]]--;
}
return result;
}
private boolean same(int[] a, int[] b){
for(int i = 0; i < 128; i++)
if(a[i] != 0 && b[i] < a[i])
return false;
return true;
}
}- Method 1: Sliding Window
class Solution { public String minWindow(String s, String t) { if(s.length() < t.length()) return ""; int slow = 0, matchNum = 0, minLen = Integer.MAX_VALUE, index = 0; Map<Character, Integer> wordDict = constructMap(t); for(int fast = 0; fast < s.length(); fast++){ char c = s.charAt(fast); if(!wordDict.containsKey(c)) continue; int freq = wordDict.get(c); wordDict.put(c, freq - 1); if(freq == 1){ matchNum++; } while(matchNum == wordDict.size()){ if(fast - slow + 1 < minLen){ minLen = fast - slow + 1; index = slow; } char left = s.charAt(slow++); if(!wordDict.containsKey(left)) continue; int count = wordDict.get(left); wordDict.put(left, count + 1); if(count == 0){ //0->1 matchNum--; } } } return minLen == Integer.MAX_VALUE ? "": s.substring(index, index + minLen); } private Map<Character, Integer> constructMap(String t){ Map<Character, Integer> map = new HashMap<>(); for(char c : t.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); } return map; } }
- Method 1: Sliding window
class Solution { public String minWindow(String s, String t) { if(s.length() < t.length()) return ""; Map<Character, Integer> map = constructMap(t); int slow = 0, matchNum = 0, minLen = Integer.MAX_VALUE, index = 0; char[] arr = s.toCharArray(); for(int fast = 0; fast < arr.length; fast++){ char c = arr[fast]; if(!map.containsKey(c)) continue; int freq = map.get(c); map.put(c, freq - 1); if(freq == 1){ matchNum++; } while(matchNum == map.size()){ if(fast - slow + 1 < minLen){ minLen = fast - slow + 1; index = slow; } char left = arr[slow++]; if(!map.containsKey(left)) continue; int count = map.get(left); map.put(left, count + 1); if(count == 0) matchNum--; } } return minLen == Integer.MAX_VALUE ? "": s.substring(index, index + minLen); } private Map<Character, Integer> constructMap(String t){ char[] arr = t.toCharArray(); Map<Character, Integer> map = new HashMap<>(); for(char c : arr){ map.put(c, map.getOrDefault(c, 0) + 1); } return map; } }