首页 > 代码库 > [leetcode] Minimum Window Substring
[leetcode] 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.
https://oj.leetcode.com/problems/minimum-window-substring/
思路:窗口移动法。 详见这里
public class Solution { public String minWindow(String S, String T) { if (S == null || T == null) return ""; int[] needToFind = new int[256]; int[] found = new int[256]; for (int i = 0; i < T.length(); i++) needToFind[T.charAt(i)]++; String result = ""; int begin = 0, end = 0; int minWin = Integer.MAX_VALUE; int count = 0; for (end = 0; end < S.length(); end++) { if (needToFind[S.charAt(end)] == 0) continue; char ch = S.charAt(end); found[ch]++; if (found[ch] <= needToFind[ch]) count++; if (count == T.length()) { //move the begin pointer while the constrain meets while (begin < S.length() && (found[S.charAt(begin)] > needToFind[S.charAt(begin)] || needToFind[S.charAt(begin)] == 0)) { if (found[S.charAt(begin)] > 0) found[S.charAt(begin)]--; begin++; } //update the min according to the current window if (end - begin + 1 < minWin) { minWin = end - begin + 1; result = S.substring(begin, end + 1); } } } return result; } public static void main(String[] args) { System.out.println(new Solution().minWindow("ADOBECODEBANC", "ABC")); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。