LEETCODE 76. Minimum Window Substring 解题思路分析

题目大意:

最小覆盖子串

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

示例:

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

说明:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=76

解题思路分析:

这是一道经典的双指针题目。我们需要在字符串S中找到一个子区间,该区间内要包含字符串T的所有字符,举个例子,如果T中有1个a,3个b,那么该S的子区间内也要包含至少1个a和3个b,另外该区间内也可以包含其他无关字符。

解题时,我们需要先遍历一遍字符串T,统计出它包含每种字符的个数。然后开始利用双指针方式遍历字符串S。初始时,左指针与右指针均处于S下标为0的位置。我们开始向右移动右指针,查看右指针所指的字符是否在T中出现过,若没出现过,继续向右移动。反之如果出现过,还需要看该字符在S中出现过的次数,如果该次数小于等于T中出现的次数,说明我们找到了一个合理的字符,此时更新一下找到的合理字符数(加一)。

当合理字符数等于字符串T的长度时,说明当前子区间(左指针到右指针范围)内包含了T的全部字符,当前区间为一个合理区间,并更新一下全局最短合理区间长度。此时开始尝试向右移动左指针,左指针划过的位置代表该字符被移除出区间范围,如果该字符存在于字符串T中,并且移除该字符后,当前区间内该字符数量小于了T中该字符的数量,说明这时区间内并不能包含所有T中的元素,合理字符数应减一,并结束移动左指针,返回继续移动右指针。反之继续移动左指针。

实现代码:

public String minWindow(String s, String t) {
    // t中每种字符的个数
    int[] count = new int[58]; 
    // 字符串S的长度
    int lengthS = s.length();
    // 字符串T的长度
    int lengthT = t.length();
    // 统计字符串T中每种字符的个数
    for(int i=0;i<lengthT;i++){
        count[t.charAt(i)-'A']++;
    }
    // 左指针,右指针
    int left=0, right=0;
    // 最小区间长度
    int minLength=Integer.MAX_VALUE;
    // 返回结果
    String res="";
    // 区间内总合理字符个数
    int countAll=0;
    // 区间内每种字符出现的个数
    int[] count2 = new int[58];
    while(right<lengthS){
        // 右指针指向的字符 
        int c = s.charAt(right)-'A';
        // 如果该字符在T中出现过
        if(count[c]>0){
            // 更新区间内该字符数量(加一)
            // 如果该数量小于等于T中出现的数量,
            // 合理字符数加一
            if(++count2[c]<=count[c]) countAll++;
        }
        // 如果合理字符数等于T的长度,此时为合理区间
        while(countAll==lengthT){
            // 如果该区间长度小于全局最小长度
            if(right-left+1<minLength){
                // 更新当前长度为最小长度
                minLength = right-left+1;
                // 当前区间子串为返回结果
                res=s.substring(left, right+1);
            }
            // 左指针指向的字符
            int cl=s.charAt(left)-'A';
            // 如果该字符在T中出现过
            if(count[cl]>0){
                // 将该字符从区间内移除,该字符区间内出现次数减一
                // 该字符区间内出现次数小于T中出现次数,区间内合理字符数量减一
                if(--count2[cl]<count[cl]) countAll--;
            }
            left++; // 移动左指针
        }
        right++; // 移动右指针
    }
    return res;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 80.45% of Java online submissions for Minimum Window Substring.

Memory Usage: 38.5 MB, less than 89.36% of Java online submissions for Minimum Window Substring.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-76-minimum-window-substring-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。