题目链接:https://leetcode.com/problems/minimum-window-substring/
方法一:
思路就是用两个HashMap进行存储,一个用于将t字符串中的
所有字符以及相对应的个数存储进来。另一个用于在迭代中比较。
控制两个指针,left和right,先让right一直向右遍历直到map中存够了t字符串中的所有值。
此时将left在向右滑动,直到map中的值不再和t字符串完全匹配。
用一个三个元素的一维数组保存 最小覆盖子串长度和left,right下标。
借用一下官方的图:
AC 23ms Java:
class Solution { public String minWindow(String s, String t) { if(s.length()==0||t.length()==0) return ""; Map<Character,Integer> dict=new HashMap(); for(int i=0;i<t.length();i++){ int value=dict.getOrDefault(t.charAt(i),0); dict.put(t.charAt(i),value+1); } int sum=dict.size(); int left=0,right=0; int count=0; int[] ans={-1,0,0}; Map<Character,Integer> window=new HashMap(); while(right<s.length()){ char c=s.charAt(right); int value=window.getOrDefault(c,0); window.put(c,value+1); if(dict.containsKey(c)&&window.get(c).intValue()==dict.get(c).intValue()) count++; while(left<=right&&count==sum){ c=s.charAt(left); if(ans[0]==-1||right-left+1<ans[0]){ ans[0]=right-left+1; ans[1]=left; ans[2]=right; } window.put(c,window.get(c)-1); if(dict.containsKey(c)&&window.get(c).intValue()<dict.get(c).intValue()) count--; left++; } right++; } return ans[0]==-1?"":s.substring(ans[1],ans[2]+1); } }
注意:window.get(c).intValue()==dict.get(c).intValue() 这里一定要加上intValue()方法(或者用equals比较)。
因为我们在HashMap中用的是Integer包装类,本质上是对象,在比较的时候会比较堆中的地址。
扩展:Integer比较不要使用==使用equals()或Integer.intValue()
方法二:比较快的一种方法。
思路和方法一相同,只不过这次并不用HashMap存储,而是用128个int型数组存储。
首先对t字符串遍历,每个t字符串中出现过的字符都会在数组中显示它出现过多少次,
然后sum=记录t的长度,接下来right指针向右遍历,如果char rc=s.charAt(right),array[rc]>0
说明该字符是在t字符串中出现过的,直到right指针停止,此时转向对left指针的判断。
考虑一个例子,(结合下面的AC代码看更好)
s=“AAACBEADC”
t=“AAC”
最初array['A']==2,array['C']==1;
right向右滑动时,到达第三个A,此时的A不应该计入有效的字符,应该到C停止。sum=0;
array['A']=-1;
然后left向右滑动,如果array['A']=0,说明到了有效字符的边界,从而sum++。
AC 2ms 98% Java:
class Solution { public String minWindow(String s, String t) { if (s.length() == 0 || t.length() == 0) { return ""; } int[] array=new int[128]; for(int i=0;i<t.length();i++){ array[t.charAt(i)]++; } int left=0,right=0,head=-1,sum=t.length(),window=Integer.MAX_VALUE; while(right<s.length()){ char rc=s.charAt(right); if(array[rc]>0){ sum--; } array[rc]--; while(sum==0){ char lc=s.charAt(left); if(window>right-left+1){ window=right-left+1; head=left; } if(array[lc]==0){ sum++; } array[lc]++; left++; } right++; } return head==-1?"":s.substring(head,head+window); } }
方法三:
对方法一进行优化:
不过个人不建议用其他的库。
import javafx.util.Pair; class Solution { public String minWindow(String s, String t) { if (s.length() == 0 || t.length() == 0) { return ""; } Map<Character, Integer> dictT = new HashMap<Character, Integer>(); for (int i = 0; i < t.length(); i++) { int count = dictT.getOrDefault(t.charAt(i), 0); dictT.put(t.charAt(i), count + 1); } int required = dictT.size(); // Filter all the characters from s into a new list along with their index. // The filtering criteria is that the character should be present in t. List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (dictT.containsKey(c)) { filteredS.add(new Pair<Integer, Character>(i, c)); } } int l = 0, r = 0, formed = 0; Map<Character, Integer> windowCounts = new HashMap<Character, Integer>(); int[] ans = {-1, 0, 0}; // Look for the characters only in the filtered list instead of entire s. // This helps to reduce our search. // Hence, we follow the sliding window approach on as small list. while (r < filteredS.size()) { char c = filteredS.get(r).getValue(); int count = windowCounts.getOrDefault(c, 0); windowCounts.put(c, count + 1); if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) { formed++; } // Try and contract the window till the point where it ceases to be 'desirable'. while (l <= r && formed == required) { c = filteredS.get(l).getValue(); // Save the smallest window until now. int end = filteredS.get(r).getKey(); int start = filteredS.get(l).getKey(); if (ans[0] == -1 || end - start + 1 < ans[0]) { ans[0] = end - start + 1; ans[1] = start; ans[2] = end; } 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); } }