[LintCode/LeetCode] Minimum Window Substring

Corwien 发布于2019-08-14 15:43 / 2474人阅读

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 characters in target, return the emtpy string "".

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

Clarification

Should the characters in minimum window has the same order in target?

Not necessary.

Example

For source = "ADOBECODEBANC", target = "ABC", the minimum window is "BANC"

Challenge

Can you do it in time complexity O(n) ?

Solution

public class Solution {
    public String minWindow(String source, String target) {
        int[] S = new int[255], T = new int[255];
        for (int i = 0; i < target.length(); i++) T[target.charAt(i)]++;
        int start = 0, left = -1, right = source.length(), match = 0, len = source.length();
        for (int i = 0; i < source.length(); i++) {
            S[source.charAt(i)]++;
            if (S[source.charAt(i)] <= T[source.charAt(i)]) match++;
            if (match == target.length()) {
                while (start < i && S[source.charAt(start)] > T[source.charAt(start)]) {
                    S[source.charAt(start)]--;
                    start++;
                }
                if (i - start < len) {
                    len = i - start;
                    left = start;
                    right = i;
                }
                S[source.charAt(start)]--;
                match--;
                start++;
            }
        }
        return left == -1 ? "" : source.substring(left, right+1);
    }
}

Solution: Updated 2018-10

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

GPU云服务器云服务器 Minimum Substring SUBSTRING_INDEX java的substring方法

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

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

[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序数组中找最小值或最大值的题目，很明显可以使用二分法。因此，只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个，中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Minimum Path Sum

摘要：遍历整个矩阵，对于，取上方和左边较小值，与相加可得该点最小值。 Problem Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You ...

CntChen 2019-08-14 15:28 评论0 收藏0
[LintCode/LeetCode] Longest Palindrome Substring

摘要：是左闭右开区间，所以要。，要理解是和之间只有一个元素。循环每次的时候，都要更新子串更大的情况。补一种中点延展的方法循环字符串的每个字符，以该字符为中心，若两边为回文，则向两边继续延展。循环返回长度最长的回文串即可。 Problem Given a string S, find the longest palindromic substring in S. You may assume ...

AaronYuan 2019-08-14 15:15 评论0 收藏0
[LintCode/LeetCode] Restore IP Addresses

摘要：第一个分割点第二个分割点第三个分割点 Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....

bingo 2019-08-14 15:14 评论0 收藏0
[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0