找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 162|回复: 2
收起左侧

[刷题记录板] 76. Minimum Window Substring

[复制链接]

23

主题

0

精华

28

积分

新米人

Rank: 1

积分
28
发表于 11-29-2016 05:41 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> map = new HashMap<>();
        
        for (int i=0;i<t.length();i++){
            int val = map.getOrDefault(t.charAt(i),0);
            map.put(t.charAt(i),val+1 );
        }
        int low=0;
        int high=0;
        int minlen = Integer.MAX_VALUE;
        int minstart=-1;
        int count=t.length();
        while (high<s.length()){
            if (map.containsKey(s.charAt(high))){
                if (map.get(s.charAt(high))>0)   count--;  
                map.put(s.charAt(high), map.get(s.charAt(high))-1 );
            }
            
            while (count==0){
                if (minlen> high-low+1 ){
                    minstart=low;
                    minlen=high-low+1;
                }
               
                if (map.containsKey(s.charAt(low))){
                    if (map.get(s.charAt(low))==0)   count++;
                    map.put(s.charAt(low), map.get(s.charAt(low))+1 );
                }
                low++;            
               
            }
   
            high++;
            
        }
        if (minstart==-1)  return "";
        return s.substring(minstart,minstart+minlen);
        
    }

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-29-2016 05:45 AM | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 12-2-2016 03:39 AM | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表