[LintCode/LeetCode] Minimum Window Substring

Corwien 發布于2019-08-14 15:43 / 2494人閱讀

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方法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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