leetcode 518，leetcode76. Minimum Window Substring

2023-10-21 阅读 32 评论 0

摘要：class Solution {public String minWindow(String s, String t) {int[] map = new int[128];for(Character ch : t.toCharArray()){map[ch]++;}//定義counter來計數,begin/end作為滑動窗口的兩端，d表示滑動窗口長度,head來記錄滿足條件的起始位置,len表示s

class Solution {public String minWindow(String s, String t) {int[] map = new int[128];for(Character ch : t.toCharArray()){map[ch]++;}//定義counter來計數,begin/end作為滑動窗口的兩端，d表示滑動窗口長度,head來記錄滿足條件的起始位置,len表示s字符串長度int counter = t.length();int begin = 0, end = 0, head = 0, d = Integer.MAX_VALUE;int len = s.length();while(end < len){//若遇到與t字符串中相同元素，計數減一if(map[s.charAt(end)] > 0){counter--;}//該元素計數減一map[s.charAt(end)]--;//滑動窗口右端后移end++;//直到窗口內包含t中所有元素while(counter == 0){//若當前滑動窗口長度較小，則記錄當前滑動窗口的長度及起始位置if(end - begin < d){d = end - begin;head = begin;//進一步優化一下，如果當前滑動窗口大小與t子串長度一樣長，直接返回結果即可。if(d == t.length()){return s.substring(head, head + d);}}//重新調整滑動窗口if(map[s.charAt(begin)] == 0){  counter++;}//恢復狀態map[s.charAt(begin)]++;//滑動窗口左端向右側移動begin++;}}return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);}
}