Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Minimum Window Substring

Leetcode algorithms 第 76 题:Minimum Window Substring。

题目

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 emtpy string “”.

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

解答

O(n)时间内找出S中最小的窗口使其包含T的全部字符。首先必须把T的全部字符记录下来,包括每个字符出现的次数。然后使用两个指针i和j对S字符串进行遍历,i记录遍历的起点,j记录遍历的终点。当遍历到某个j时i到j之间包含了T的所有字符,这时尽量把i向前移以减小窗口的长度。然后i从新的位置开始,使j继续遍历,直到终点为止。

具体代码如下:

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.empty() || T.empty()) return "";
        
        int l1 = S.size(), l2 = T.size(), cnt1[256] = {0}, cnt2[256] = {0};
        for (int i = 0; i < l2; i++) cnt2[T[i]]++; //记录T每个字符出现的次数
        
        int st, ed, len = INT_MAX, cnt = 0;
        for (int i = 0, j = 0; j < l1; j++) //双指针同时扫描,i为起点,j为终点
        {
            if (++cnt1[S[j]] <= cnt2[S[j]]) cnt++; 
            if (cnt == l2) //包含全部
            {
                while (cnt1[S[i]] > cnt2[S[i]]) cnt1[S[i++]]--;
                if (j-i+1 < len) len = j-i+1, st = i, ed = j;
            }
        }
        return len == INT_MAX ? "" : S.substr(st, ed - st + 1);
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论