本文共 2899 字，大约阅读时间需要 9 分钟。
LeetCode刷题：76. 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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC" Note:If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC" 说明：如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。算法设计
下面是参考LeetCode讲解的算法设计：
这个问题要求我们返回字符串S中的最小窗口，它包含字符串T的所有字符。如果一个窗口包含有T的所有字符，我们就称它为"期望窗口"。
我们可以使用一个简单的滑动窗口方法来解决这个问题。
在任何基于滑动窗口的问题中，我们都有两个指针。一个右指针，其任务是展开当前窗口，然后我们有一个左指针，其任务是收缩给定窗口。在任何时间点，只有一个指针移动，另一个指针保持不变。
我们一直通过移动右指针来扩展窗口。当窗口具有所有需要的字符时，我们收缩（如果可能）并保存到目前为止最小的窗口。
答案是最小的理想窗口。
例如 s=“abaacbab” t=“abc”。然后我们的回答窗口是“ACB”，下面显示的是可能需要的窗口之一。
给出算法代码如下：
package com.bean.algorithm.basic;import java.util.HashMap;import java.util.Map;public class MinimumWindowSubstring { public String minWindow(String s, String t) { if (s.length() == 0 || t.length() == 0) { return ""; } // 保存t中所有唯一字符计数的字典。 Map dictT = new HashMap (); for (int i = 0; i < t.length(); i++) { int count = dictT.getOrDefault(t.charAt(i), 0); dictT.put(t.charAt(i), count + 1); } // t中的唯一字符数，需要出现在所需的窗口中。 int required = dictT.size(); // 左 右 指针 int l = 0, r = 0; /* * formed 用于跟踪当前窗口中以其所需频率存在多少个唯一字符。 例如 如果t是“AABC”那么窗口必须有两个A，一个B和一个C. * 因此，当满足所有这些条件时，formed = 3。 */ int formed = 0; // 字典，用于保存当前窗口中所有唯一字符的计数。 Map windowCounts = new HashMap (); // (窗口长度, 左指针, 右指针) int[] ans = { -1, 0, 0 }; while (r < s.length()) { // 从右侧向窗口添加一个字符 char c = s.charAt(r); int count = windowCounts.getOrDefault(c, 0); windowCounts.put(c, count + 1); // 如果添加的当前字符的频率等于t中的所需计数，则将formed增加1。 if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) { formed++; } // 尝试并收缩窗口，直到它不再是“理想的”。 while (l <= r && formed == required) { c = s.charAt(l); // 更新满足条件的最小的窗口和 l r 指针 if (ans[0] == -1 || r - l + 1 < ans[0]) { ans[0] = r - l + 1; ans[1] = l; ans[2] = r; } // Left”指针指向的位置处的字符不再是窗口的一部分。 windowCounts.put(c, windowCounts.get(c) - 1); if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) { formed--; } // 将左指针向前移动，这将有助于查找新窗口。 l++; } // 继续扩大窗口 r++; } return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1); } public static void main(String[] args) { // TODO Auto-generated method stub //Input: S = "ADOBECODEBANC", T = "ABC" // Output: "BANC" MinimumWindowSubstring mws=new MinimumWindowSubstring(); String s="ADOBECODEBANC"; String t="ABC"; String result = mws.minWindow(s, t); System.out.println("result is: "+result); }} 程序运行结果：
result is: BANC
转载地址：http://untdi.baihongyu.com/