国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

[LeetCode] 727. Minimum Window Subsequence

kaka / 3525人閱讀

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);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/72569.html

相關(guān)文章

  • Longest Increasing Subsequence

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

    FullStackDeveloper 評(píng)論0 收藏0

  • LeetCode[300] Longest Increasing Subsequence

    摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L(zhǎng)的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長(zhǎng)的。保證升序相等也要替換這個(gè)值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

    blankyao 評(píng)論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 評(píng)論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 評(píng)論0 收藏0

  • [Leetcode] Minimum Window Substring 最小字符串窗口

    摘要：雙指針?lè)◤?fù)雜度時(shí)間空間思路用一個(gè)哈希表記錄目標(biāo)字符串每個(gè)字母的個(gè)數(shù)，一個(gè)哈希表記錄窗口中每個(gè)字母的個(gè)數(shù)。先找到第一個(gè)有效的窗口，用兩個(gè)指針標(biāo)出它的上界和下界。 Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the...

    Yuanf 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<