Finley.Hamilton

# 题目

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.

# 代码

``````public class Solution {
Map<Character, Integer> map = new HashMap<Character, Integer>();

public String minWindow(String S, String T) {
int i = 0;
int j = 0;

int[] count = new int[128];
int minWindows = Integer.MAX_VALUE;
String minWindowString="";

for (char c : T.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, 0);
}
map.put(c, map.get(c) + 1);
}

for (; j < S.length(); j++) {
if (contain(count, T)) {
for (; i <= j; i++) {
if (!contain(count, T)) {
break;
} else {
if(minWindows > j-i) {
minWindows = j-i;
minWindowString = S.substring(i,j);
}

}
// contains i in this iteration
count[S.charAt(i)]--;
}
}
// do not contains j in this iteration
count[S.charAt(j)]++;
}

for (; i < j; i++) {
if (!contain(count, T)) {
break;
} else {
if(minWindows > j-i) {
minWindows = j-i;
minWindowString = S.substring(i,j);
}
}
count[S.charAt(i)]--;
}

// System.out.println(minWindowString);
if (i == 0) {
return "";
}
return minWindowString;
}

private boolean contain(int[] count, String t) {
for (char character : map.keySet()) {
if (count[character] < map.get(character)) {
return false;
}
}
return true;
}
}
``````

### Finley.Hamilton

Codeforces 886D - Restoration of string

2017/11/16
0
0
poj1743 Musical Theme【后缀数组+二分答案】

cdsszjj
01/28
0
0
［LeetCode］Degree of an Array 数组的度

2017/12/01
0
0

02/24
0
0
KMP字符串匹配算法

KMP算法，Knuth-Morris-Pratt Algorithm，一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人提出的一种快速模式匹配算法。 KMP朴素算法 原理：子串pattern依次与目标串tar...

2013/01/06
177
0

Nginx-使用简单总结

Java搬砖工程师
10分钟前
1
0

11分钟前
1
0
Underscore _.template 方法使用详解

https://github.com/hanzichi/underscore-analysis/issues/26 前文 浅谈 Web 中前后端模板引擎的使用 我们简单了解了模板引擎在前后端的应用场景，本文重点深入 Underscore 的模板函数 _.te...

12分钟前
0
0

function string10to64 (number) { var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_\$'.split(''), radix = chars.length, qutient =......

12分钟前
0
0

13分钟前
0
0