题目
- 原题链接：76. 最小覆盖子串
1- 思路
利用两个哈希表解决分为 ：① 初始化哈希表、②遍历 s，处理当前元素，判断当前字符是否有效、③收缩窗口、④更新最小覆盖子串
2- 实现
⭐76. 最小覆盖子串——题解思路
class Solution {public String minWindow(String s, String t) {// 定义两个 HashMapHashMap<Character,Integer> hs = new HashMap<>();HashMap<Character,Integer> ht = new HashMap<>();// 定义 int cnt = 0;String res = "";// 初始化 htfor(int i = 0 ; i < t.length();i++){char c = t.charAt(i);ht.put(c,ht.containsKey(c) ? ht.get(c)+1:1);}// 遍历 sfor(int i = 0, j = 0 ; i < s.length();i++){char c = s.charAt(i);hs.put(c, hs.containsKey(c) ? hs.get(c)+1 : 1);// 判断 i 合法if(ht.containsKey(c) && hs.get(c) <= ht.get(c)) cnt++;// 缩小区间while (j <= i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))) {hs.put(s.charAt(j), hs.get(s.charAt(j ++)) - 1);}// 3 收集结果// 首先是必须等于 cnt && (hs.length()> (i-j+1) || res.length()<1)if(cnt==t.length() && ( res.length() > (i-j+1) || res.length()<1)){res = s.substring(j,i+1);}}return res;}
}
3- ACM 实现
public class minWindow {public static String minWindow(String s,String t){// 1.数据结构HashMap<Character,Integer> ht = new HashMap<>();HashMap<Character,Integer> window = new HashMap<>();int cnt = 0;String res = "";// 2.遍历 t 初始化 htfor(int i = 0 ; i < t.length();i++){char c = t.charAt(i);ht.put(c,ht.containsKey(c)? ht.get(c)+1:1);}// 3.遍历 sfor(int i = 0,j=0 ; i < s.length();i++){char cc = s.charAt(i);window.put(cc,window.containsKey(cc)? window.get(cc)+1:1);// 判 cc 断有效性// 在 ht 中if(ht.containsKey(cc) && window.get(cc) <=ht.get(cc)) cnt++;// 窗口收缩while(j<=i && (!ht.containsKey(s.charAt(j)) || window.get(s.charAt(j)) > ht.get(s.charAt(j)))){window.put(s.charAt(j),window.get(s.charAt(j++))-1);}// 更行 resif(cnt == t.length() && (res.length()>(i-j+1) || res.length()<1)){res = s.substring(j,i+1);}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入字符串1");String s = sc.nextLine();System.out.println("输入字符串2");String t = sc.nextLine();String res = minWindow(s,t);System.out.println("结果是"+ res);}
}