Leetcode[76] Minimum Window Substring

suemi 发布于2019-08-16 10:26 / 904人阅读

LeetCode[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".

Hash Table + Two Pointer

复杂度
O(N),O(N)

思路
类似two pointer的想法。每次维护一个窗口。

代码

public String minWindow(String s, String t) {
    int start = 0, len = Integer.MAX_VALUE;
    int[] times = new int[256];
    int[] stimes = new int[256];
    for(int i = 0; i < t.length(); i ++) {
        times[t.charAt(i)] ++;
    }
    int cnt = 0;
    int begin = -1, end = 0;
    for(int i = 0; i < s.length(); i ++) {
        char ch = s.charAt(i);
        stimes[ch] ++;
        if(stimes[ch] <= times[ch]) cnt ++;
        if(cnt == t.length()) {
            while(start < s.length() && stimes[s.charAt(start)] > times[s.charAt(start)]) {
                stimes[s.charAt(start)] --;
                start ++;
            }
            //
            if(i - start + 1 < len) {
                begin = start;
                end = i;
                len = i - start + 1;
            }
            stimes[s.charAt(start)] --;
            start ++;
            cnt --;
        }
    }
    return begin == -1 ? "" : s.substring(begin, end + 1);
}

云服务器 GPU云服务器 Minimum 服务器ipv76 LeetCode Substring

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69806.html

leetcode-76-Minimum Window Substring

摘要：逐步逼近法，类似于牛顿迭代法。重点是找到规律，然后将规律加以表示。动态规划，相邻两个位置之间的关系。字符串的叠加，可以增加共性，通过相减可以得到边界位置处符合规律的要求。学会将问题转化为可求的边界问题。吃透题目：任何问题的解决在于理解题目，挖掘本质。这道题目，从一个string中找包含char的最小子序列，O(n)，要求只能遍历一遍。每次移动一个index，都尝试找子序列，通...

edagarli 2019-07-31 11:10 评论0 收藏0
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 评论0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因为我们需要的是最值，中间值我们不在乎，所以一次收敛到最小。下面来三个需要查重并且记录上次出现的位置，选择以为例，走到用做检查，发现出现过，把移到的下一个。是上个题目的简易版，或者特殊版。这里聊一聊解一类问题，就是满足某一条件的substring最值问题。最开始我们以Minimum Window Substring为例，并整理总结leetcode里所有类似题目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 评论0 收藏0
[Leetcode] Minimum Window Substring 最小字符串窗口

摘要：双指针法复杂度时间空间思路用一个哈希表记录目标字符串每个字母的个数，一个哈希表记录窗口中每个字母的个数。先找到第一个有效的窗口，用两个指针标出它的上界和下界。 Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the...

Yuanf 2019-08-14 12:26 评论0 收藏0
[LeetCode] 727. Minimum Window Subsequence

Problem Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string...

kaka 2019-08-16 13:55 评论0 收藏0