给你一个字符串 S, 一个字符串 T, 请在字符串 S 里面找出: 包含 T 所有字母的最小子串.
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
如果 S 中不存这样的子串, 则返回空字符串 "".
如果 S 中存在这样的子串, 我们保证它是唯一的答案.
- class Solution {
- public String minWindow(String s, String t) {
- if(s == null || t == null || s.length() <t.length()) return "";
- HashMap<Character,Integer> need = new HashMap<>();
- for(int i = 0;i <t.length();i++){
- char c = t.charAt(i);
- need.put(c,need.getOrDefault(c,0) + 1);
- }
- int l = 0,r = 0;
- int ans_l = 0,ans_r = -1,ans_len = Integer.MAX_VALUE;
- // 遍历
- while(r < s.length()){
- char cr = s.charAt(r);
- if(need.containsKey(cr)){
- need.put(cr,need.get(cr) - 1);
- // 假如覆盖了
- while(match(need)){
- // 记录长度
- int curLen = r - l + 1;
- if(curLen < ans_len){
- ans_len = curLen;
- ans_l = l;
- ans_r = r;
- }
- // 更新左指针
- char cl = s.charAt(l);
- if(need.containsKey(cl)){
- need.put(cl,need.get(cl) + 1);
- }
- l++;
- }
- }
- r++;
- }
- return s.substring(ans_l,ans_r + 1);
- }
- private boolean match(Map<Character,Integer> map){
- for(int num : map.values()){
- if(num> 0) return false;
- }
- return true;
- }
- }
来源: http://www.bubuko.com/infodetail-3501369.html