题解 | #最小覆盖子串#

最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        Map<Character,Integer> s_map = new HashMap<>();
        Map<Character,Integer> t_map = new HashMap<>();
        //T中的数据存入t_map
        for(int i = 0;i<T.length();i++){
            t_map.put(T.charAt(i), t_map.containsKey(T.charAt(i)) ? t_map.get(T.charAt(i))+1 : 1 );
        }
        int left = 0;
        int right = 0;
        int result_length = Integer.MAX_VALUE;
        String ans = "";
       while(right < S.length()){
           s_map.put(S.charAt(right), s_map.containsKey(S.charAt(right)) ? s_map.get(S.charAt(right)) +1 : 1 );
           while(isCover(s_map,t_map)){
               if(result_length > right - left +1){
                   result_length = right - left +1;
                   ans = S.substring(left,right+1);
               }
                s_map.put(S.charAt(left), s_map.get(S.charAt(left)) - 1 );
                if(s_map.get(S.charAt(left)) == 0){
                    s_map.remove(S.charAt(left));
                }
                left++;
           }
           right++;
       }
        return ans;
    }

    public boolean isCover(Map<Character,Integer> s_map,Map<Character,Integer> t_map){
        for(Character key : t_map.keySet()){
            if(!s_map.containsKey(key)){
                return false;
            }else if(s_map.get(key) < t_map.get(key)){
                return false;
            }
            
        }
        return true;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务