本文共 1690 字,大约阅读时间需要 5 分钟。
Minimum Window Substring
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.
Java代码:public class Solution {public String minWindow(String S, String T) { int[] result = new int[] {-1, S.length()}; int counter = 0; Mapexpected = new HashMap<>(); Map window = new HashMap<>(); for (int i = 0; i < T.length(); i++) { if (!expected.containsKey(T.charAt(i))) expected.put(T.charAt(i), 0); expected.put(T.charAt(i), expected.get(T.charAt(i)) + 1); } for (int i = 0, j = 0; j < S.length(); j++) { char cur = S.charAt(j); if (expected.containsKey(cur)) { if (!window.containsKey(cur)) window.put(cur, 0); window.put(cur, window.get(cur) + 1); if (window.get(cur) <= expected.get(cur)) counter++; if (counter == T.length()) { char remove = S.charAt(i); while (!expected.containsKey(remove) || window.get(remove) > expected.get(remove)){ if (expected.containsKey(remove)) window.put(remove, window.get(remove) - 1); remove = S.charAt(++i);; } if (j - i < result[1] - result[0]) result = new int[]{i, j}; } } } return result[1] - result[0] < S.length() ? S.substring(result[0], result[1] + 1) : "";}}
转载地址:http://mvuni.baihongyu.com/