leetcode 76-Minimum Window Substring(hard)

2021-07-10 02:07

阅读：681

标签：character 情况 cte osi tar ber [] length public

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

cases:

when stand on the ith position of S:

1. if the character is not in T, do nothing;

2. if the character is in T:

　　start->i contains all characters in T:

　　　　S[start] not in T or ((frequency of S[start] in start->i) > (frequency of S[start] in T)) start++

　　　　maxlen=max(i-start+1,maxlen), start++

use hashmap or int[256/128] to record the number of characters in t, int[] record is better.

class Solution {
    public String minWindow(String s, String t) {
        int[] cnum=new int[256];
        int count=t.length();
        for(char c:t.toCharArray()){
            cnum[c]++;
        }
        int start=0;
        int l=0;
        int minlen=Integer.MAX_VALUE;
        for(int r=0;r){
            if(cnum[s.charAt(r)]>0){
                count--;
            }
            cnum[s.charAt(r)]--;
            if(count==0){
                while(cnum[s.charAt(l)]){
                    cnum[s.charAt(l)]++;
                    l++;
                }
                if(r-l+1minlen){ 
                    minlen=r-l+1;
                    start=l;
                    cnum[s.charAt(l)]++;
                    count++;
                    l++;
                }
            }
        }
        return (minlen== Integer.MAX_VALUE)?"":s.substring(start,start+minlen);
    }
}

注意不要老是笔误s.charAt()写成s.charAt[]！

cnum的index是字母的asc码，不要误写出cnum[l/r]之类，而是cnum[s.charAt(l/r)]！

return的时候不要掉以轻心，不要忘了如果没有满足条件的解的情况！

leetcode 76-Minimum Window Substring(hard)

标签：character 情况 cte osi tar ber [] length public

原文地址：https://www.cnblogs.com/yshi12/p/9689915.html

上一篇：ToolTip C#

下一篇：C#下使用XmlDocument详解

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：leetcode 76-Minimum Window Substring(hard)
文章链接：http://soscw.com/essay/103032.html

亲，登录后才可以留言！

leetcode 76-Minimum Window Substring(hard)

评论

热门文章

推荐文章

最新文章

置顶文章