LeetCode 76. Minimum Window Substring题目解析-wowAC

Description

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).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

题目复述

给定一个字符串S,和字符串T,找到S中长度最小的一个子串,使得该子串包含T中所有字符,要求算法复杂度为O(n)。

如果找不到返回"",保证只有一个答案。

题目解析

注意T中的字符可能重复,考虑使用尺取法,首先求出以0位置开头的子串,然后再求以1为开头依次类推,在求解的过程中可以重复使用之前的信息。用[i – j]表示以i开头满足要求的子串,hash1表示子串中的字符个数,hash2表示T中的字符个数,numappear子串已经匹配T的字符个数。注意程序中numappear增加和减少的条件。

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        int i = 0, j = -1;
        int num_appear = 0;   //i - j内出现的t的字符的个数
        int hash1[300], hash2[300];  //分别是[i, j]字母出现的次数和t中出现的字母
        memset(hash1, 0, sizeof(hash1));
        memset(hash2, 0, sizeof(hash2));
        for(int i=0; i<t.length(); i++) hash2[t[i]] += 1;
        
        while(1) {
            while(j+1<s.length()&&num_appear<t.length()) {
                hash1[s[j+1]] += 1;
                if(hash1[s[j+1]] == hash2[s[j+1]])//numappear增加的条件
                    num_appear += hash2[s[j+1]];
                j++;
            }
            //更新答案
            if(num_appear==t.length() && (res=="" || res.length() > j-i+1))
                res = s.substr(i, j-i+1);
            if(i == s.length()) break;    //所有以i为开头的子串求解完毕
            hash1[s[i]]--;
            if(hash1[s[i]]==hash2[s[i]]-1)  //numappear减少的条件
                num_appear-=hash2[s[i]];
            i++;
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注