[LeetCode] 727. Minimum Window Subsequence

kaka 发布于2019-08-16 13:55 / 3279人阅读

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

服务器托管海外云主机 Subsequence Minimum LeetCode LeetCode_String

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

转载请注明本文地址：https://www.ucloud.cn/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