[LeetCode] 727. Minimum Window Subsequence

kaka 發布于2019-08-16 13:55 / 3518人閱讀

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 "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

Input:
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation:
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.

Note:

All the strings in the input will only contain lowercase letters.
The length of S will be in the range [1, 20000].
The length of T will be in the range [1, 100].

Solution

class Solution {
    public String minWindow(String S, String T) {
        int m = S.length(), n = T.length();
        if (m < n) return "";
        int[][] dp = new int[m][n];
        //find the subsequence start index
        for (int i = 0; i < m; i++) {
            if (S.charAt(i) == T.charAt(0)) dp[i][0] = i;
            else {
                if (i == 0) dp[i][0] = -1;
                else dp[i][0] = dp[i-1][0];
            }
        }
        
        //initialize all dp[0][j] (j != 0) to -1
        for (int j = 1; j < n; j++) {
            dp[0][j] = -1;
            for (int i = 1; i < m; i++) {
                if (S.charAt(i) == T.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        //initialize len to an impossible large value
        int start = 0, len = m+1;
        for (int i = n-1; i < m; i++) {
            if (dp[i][n-1] != -1) {
                if (i-dp[i][n-1]+1 < len) {
                    len = i-dp[i][n-1]+1;
                    start = dp[i][n-1];
                }
            }
        }
        
        if (len == m+1) return "";
        return S.substring(start, start+len);
    }
}

GPU云服務器云服務器 Subsequence Minimum LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72569.html

Longest Increasing Subsequence

摘要：題目鏈接主要兩種方法和用，就是每次找出為結尾的最長的串的長度就好了。所以分解成就是，這個復雜度是。用一個數組，表示的長度為，表示長度為的，最右邊的可能的最小值。這里只要求長度即可，那就直接用就可以了，整個用個數組就行了。 Longest Increasing Subsequence 題目鏈接：https://leetcode.com/problems... 主要兩種方法：dp和gree...

FullStackDeveloper 2019-08-14 17:23 評論0 收藏0
LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找當前值應該在排好序的數組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數組中替換成已經排好序的，會能保證得到的結果是最長的。保證升序相等也要替換這個值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 評論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[76] Minimum Window Substring

LeetCode[76] Minimum Window Substring Given a string S and a string T, find the minimum window in S whichwill contain all the characters in T in complexity O(n). For example, S = ADOBECODEBANC T = AB...

suemi 2019-08-16 10:26 評論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