Leetcode刷题java之76. 最小覆盖子串

客官°小女子只卖身不卖艺 2023-07-04 11:18 5阅读 0赞

执行结果：

通过

显示详情

执行用时 :5 ms, 在所有 Java 提交中击败了83.91% 的用户

内存消耗 :36.3 MB, 在所有 Java 提交中击败了94.95%的用户

题目：

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"  
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。  
如果 S 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-window-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

滑动窗口，这道题细节比较多，需要自己写一写

代码：

class Solution {
        public String minWindow(String s, String t) {
            if(s.length()<=0||s==null)
            {
                return "";
            }
            int[] needs=new int[58];
            int[] windows=new int[58];
            int start=0;
            int minlen=Integer.MAX_VALUE;
            int left=0;
            int right=0;
            int count=t.length();
            for(char c:t.toCharArray())
            {
                needs[c-'A']++;
            }
            while(right<s.length())
            {
                char R=s.charAt(right);
                if(needs[R-'A']>0)
                {
                    windows[R-'A']++;
                    if(windows[R-'A']<=needs[R-'A'])
                    {
                        count--;
                    }
                }
                while(count==0)
                {
                    if(right-left+1<minlen)
                    {
                        start=left;
                        minlen=right-left+1;
                    }
                    char L=s.charAt(left);
                    if(needs[L-'A']>0)
                    {
                        windows[L-'A']--;
                        if(windows[L-'A']<needs[L-'A'])
                        {
                            count++;
                        }
                    }
                    left++;
                }
                right++;
            }
            return minlen==Integer.MAX_VALUE?"":s.substring(start,start+minlen);
        }
    }