minimum-window-substring
题目:链接
解题思路:
链接:https://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac
来源:牛客网主要思路是通过两次遍历找到所有可能的窗口(即从S中从start到end包含一个T),通过以下几个步骤实现:为了减少时间复杂度,用map记录T中所有字符出现的次数,使用count在S中寻找时计数,一旦找到一个T中的字符就count++,同时map中当前字符的次数减1,当count等于T的长度时,即找到了一个包含T的字符串,然后通过比较每个找到的字符串的长度,选择最短字符串,即为题中所求
public class Solution {
public String minWindow(String S, String T) {
if (S == null || S.length() < 1 || T == null || T.length() < 1) {
return "";
}
int[] n = new int[128];
for (char c : T.toCharArray()) {
n[c]++;
}
int end = 0, begin = 0, d = Integer.MAX_VALUE, head = 0, cnt = T.length();
while (end < S.length()) {
if (n[S.charAt(end++)]-- > 0) {
cnt--;
}
while (cnt == 0) {
if (end - begin < d) {
d = end - (head = begin);
}
if (n[S.charAt(begin++)]++ == 0) {
cnt++;
}
}
}
return d == Integer.MAX_VALUE ? "" : S.substring(head, head + d);
}
}