记录最小覆盖子串

1.暴力解法

(1)枚举输入字符串s的所有长度大于等于T的子串;

(2)逐个判断这些子串中,那些覆盖了字符串T的所有字符;

(3)在枚举的过程中,记录符合条件的,长度最短的那个子串

2.带自己备注的滑动窗口解法

class Solution {
    public String minWindow(String s, String t) {
int sLen=s.length();
int tLen=t.length();
if(sLen==0||tLen==0||sLen<tLen){
    return "";
}

char[] charArrayS=s.toCharArray();
char[] charArrayT=t.toCharArray();

int[] winFreq=new int[128];
int[] tFreq=new int [128];
for(int c:charArrayT){
    tFreq[c]++;
}

int distance=0;//滑动窗口中包含多少个T中的字符的总数
int minLen=sLen+1;
int begin=0;

int right=0;
int left=0;

while(right<sLen){

if(tFreq[charArrayS[right]]==0){//如果S中右边界的的字符在T中为0;就把区间向右移动
right++;
continue;//只有满足上面的条件这里就直接开始一个新的循环
}

//只有右边界的字符在T中是存在的并且滑动窗口winFerq的字符数是小于T中的,就可以给distance中++
if(winFreq[charArrayS[right]]<tFreq[charArrayS[right]]){
distance++;
}

winFreq[charArrayS[right]]++;//给窗口的各个字符数进行记录增加
right++;

while(distance==tLen){//这一层循环在内部,当相等之后,就说明已经够了,这下只需要优化来找最小的字符串
if(right-left<minLen){
    minLen=right-left;
    begin=left;
}

if(tFreq[charArrayS[left]]==0){//如果S中左边界的的字符在T中为0;就把区间向左移动,因为把无关紧要的字符删除可以寻找最小的字符
    left++;
    continue;//只有满足上面的条件这里就直接开始一个新的循环
}

//只有左边界的字符在T中是存在的并且滑动窗口的字符数是等于T中的,就可以给distance中--
if(winFreq[charArrayS[left]]==tFreq[charArrayS[left]]){//搞不懂,好像是由于上一次的下面对滑动窗口的值--后,导致了这里的左边界字符数相同,所以这里要对distance--,关键是这一句代码和下一句代码的顺序问题!
distance--;
}

winFreq[charArrayS[left]]--;//给窗口的各个字符数进行记录减少,这里如果对下一次造成了影响,就会distance--
left++;
}
}
if(minLen==sLen+1){
    return "";
}
return s.substring(begin,begin+minLen);
    }
    
}

侵删

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-27 14:35
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议