Leetcode:NO.76 最小覆盖子串 窗口移动

05/24 11:25
阅读数 674

题目

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

示例:

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

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

链接:https://leetcode-cn.com/problems/minimum-window-substring

解题记录

  • 通过两个指针构造一个窗口
  • 先左指针已到最近匹配字符,作为起点
  • 右指针向右移动,记录匹配字符,当匹配字符个数满足要求,比较大小记录位置
  • 此时移动左指针到符合匹配数的那个匹配字符处
  • 再次移动右指针,符合要求,记录,直到右指针越界
/**
 * @author ffzs
 * @describe
 * @date 2020/5/23
 */
public class Solution {
    public String minWindow(String s, String t) {
        char[] scl = s.toCharArray(), tcl = t.toCharArray();
        int[] ori = new int[128];
        for (char tc: tcl) ori[tc]++;
        int[] count = new int[128];
        int left=-1, right=0, min=Integer.MAX_VALUE;
        int[] res = new int[2];
        while (right < s.length()) {
            if (check(tcl, scl[right])) {
                if(left==-1) left=right;
                count[scl[right]]++;
                if (check(ori, count, tcl)) {
                    if(min > right-left) {
                        min = right - left;
                        res[0] = left;
                        res[1] = right+1;
                    }
                    count[scl[left]]--;
                    left++;
                    while (left<=right) {
                        if(check(tcl, scl[left])) {
                            if(check(ori, count, tcl)) {
                                if(min > right-left) {
                                    min = right - left;
                                    res[0] = left;
                                    res[1] = right+1;
                                }
                                count[scl[left]]--;
                            }else{
                                break;
                            }
                        }
                        left++;
                    }
                }
            }
            right++;
        }
        return s.substring(res[0], res[1]);
    }

    private boolean check (char[] tcl, char s) {
        for (char t: tcl) {
            if (t==s) return true;
        }
        return false;
    }

    private boolean check (int[] ori, int[] count, char[] tcl) {
        for(char tc: tcl) {
            if (count[tc]<ori[tc]) return false;
        }
        return true;
    }
}

class test {
    public static void main(String[] args) {
        Solution sl = new Solution();
        String s = "cabefgecdaecf";
        String t = "cae";
        System.out.println(sl.minWindow(s, t));
    }
}

在这里插入图片描述

优化

上面写得比较渣,勉强及格,分析了一下问题,主要是两个check部分比较费时间,经过思考,有两点优化:

  • 对于是否符合要求,可以根据通过数量记录,如果右符合要求的字符,那么数量减一,直到数量为0,说明匹配
  • 可以直接在ori上进行操作,如果大于0便是需要匹配字符,这样可以减少很多逻辑上的判断
  • 因为取的是最有解,因此每回判断大小的时候也不需要优选到最有情况,这样逻辑上更简单
/**
 * @author ffzs
 * @describe
 * @date 2020/5/23
 */

public class Solution {
    public String minWindow(String s, String t) {
        char[] scr = s.toCharArray(), tcr = t.toCharArray();
        int min = scr.length + 1, left = 0, right = 0, res = 0, count = tcr.length;
        int[] ori = new int[128];
        for (char c : tcr) ori[c]++;
        while (right < scr.length) {
            if (ori[scr[right]] > 0) {
                count--;
            }
            ori[scr[right]]--;
            right++;

            while (count == 0) {
                ori[scr[left]]++;
                if (ori[scr[left]] > 0) {
                    if (right - left < min) {
                        min = right - left;
                        res = left;
                    }
                    count++;
                }
                left++;
            }
        }
        return  min==scr.length+1? "" : s.substring(res, res + min);
    }
}

class test {
    public static void main(String[] args) {
        Solution sl = new Solution();
        String s = "aancc";
        String t = "ca";
        System.out.println(sl.minWindow(s, t));
    }
}

在这里插入图片描述

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部