Massive Algorithms: LeetCode 727 - Minimum Window Subsequence

LeetCode 727 - Minimum Window Subsequence

http://www.cnblogs.com/lightwindy/p/8486724.html

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequenceof 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].

At time j, for each position e in S (e for end), let's remember the largest index cur[e] = s (for start) so that S[s: e+1] has T[:j] as a subsequence, and -1 (or None) otherwise if it isn't possible.

To update our knowledge as j += 1, if S[i] == T[j], then new[e] is last, the largest s we have seen so far (representing that T[:j] was found). We can prove this is just the most recent valid index we have seen.

At the end, we find the best answer: cur[e] = s means there was a window S[s: e+1]. In Python, we use cur and new, while in Java we use dp[j] and dp[~j] to keep track of the last two rows of our dynamic programming.

public String minWindow(String S, String T) {
int[][] dp = new int[2][S.length()];
for (int i = 0; i < S.length(); ++i)
dp[0][i] = S.charAt(i) == T.charAt(0) ? i : -1;
for (int j = 1; j < T.length(); ++j) {
int last = -1;
Arrays.fill(dp[j & 1], -1);
for (int i = 0; i < S.length(); ++i) {
if (last >= 0 && S.charAt(i) == T.charAt(j))
dp[j & 1][i] = last;
if (dp[~j & 1][i] >= 0)
last = dp[~j & 1][i];
}
}
int start = 0, end = S.length();
for (int e = 0; e < S.length(); ++e) {
int s = dp[~T.length() & 1][e];
if (s >= 0 && e - s < end - start) {
start = s;
end = e;
}
}
return end < S.length() ? S.substring(start, end+1) : "";
}

https://www.jianshu.com/p/beaa7079a0fb

用dynamic programing来做，dp[i][j]表示T[0, j]是S[0,i]的subsequence, 所以我们的目标函数就是min(i-dp[i][n-1]) for all i < m

    public String minWindow(String S, String T) {
        int m = T.length(), n = S.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j + 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (T.charAt(i - 1) == S.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
            }
        }
        }

        int start = 0, len = n + 1;
        for (int j = 1; j <= n; j++) {
            if (dp[m][j] != 0) {
                if (j - dp[m][j] + 1 < len) {
                    start = dp[m][j] - 1;
                    len = j - dp[m][j] + 1;
                }
            }
        }
        return len == n + 1 ? "" : S.substring(start, start + len);
    }

http://www.cnblogs.com/lightwindy/p/8486724.html

给定字符串S和T，在S中寻找最小连续子串W，使得T是W的子序列。如果没有找到返回""，如果找到多个最小长度的子串，返回左 index 最小的。

解法1：暴力搜索brute force，对于每一个s[i]，从s[0]到s[i]扫描，看是否按顺序满足目标字符。显然要超时，不是题目要求的。

解法2： 动态规划DP, 二维数组dp[i][j]表示T[0...i]在S中找到的起始下标index，使得S[index, j]满足目前T[0...i]。首先找到能满足满足T中第一个字符T[0]的S中的字符下标存入dp[0][j]，也就是满足第一个字符要求一定是从这些找到的字符开始的。然后在开始找第二个字符T[1]，扫到的字符dp[j]存有index，说明可以从这里记录的index开始，找到等于T[1]的S[j]就把之前那个index存进来，说明从这个index到j满足T[0..1]，一直循环，直到T中的i个字符找完。如果此时dp[i][j]中有index，说明S[index, j]满足条件，如有多个输出最先找到的。

State: dp[i][j]，表示在S中找到的起始下标 index ，使得 S[index...j] 满足目前 T[0...i] 是其子序列。

function: dp[i+1][k] = dp[i][j] if S[k] = T[i+1] , 如果查看到第i+1行（也就是第 T[i+1] 的字符），如果满足S[k] = T[i+1]，就把上一行找到的index赋给它。

Initialize: dp[0][j] = j if S[j] = T[0] , 二维数组的第一行，如果字符S[j] = T[0]，就把S[j]的index(就是j)付给它。其他元素均为 None 或者 -1。

Return: dp[len(T) - 1][j], if dp[len(T) - 1][j] != None，返回最小的。如果没有返回 ""

由于我们只用到前一行的值，所以可以只用2行的二维数组，每一个循环更新其中的一行。可以用 j % 2 来往复使用。

sss

public String minWindow(String S, String T) {
    int m = T.length(), n = S.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int j = 0; j <= n; j++) {
            dp[0][j] = j + 1;
    }
    for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                    if (T.charAt(i - 1) == S.charAt(j - 1)) {
                            dp[i][j] = dp[i - 1][j - 1];
                    } else {
                            dp[i][j] = dp[i][j - 1];
            }
    }
    }
    int start = 0, len = n + 1;
    for (int j = 1; j <= n; j++) {
            if (dp[m][j] != 0) {
                    if (j - dp[m][j] + 1 < len) {
                            start = dp[m][j] - 1;
                            len = j - dp[m][j] + 1;
                    }
            }
    }
    return len == n + 1 ? "" : S.substring(start, start + len);
}

Java: DP, Time O(s*t), Space O(s*2)

public String minWindow(String S, String T) {
        int[][] dp = new int[2][S.length()];
        for (int i = 0; i < S.length(); ++i)
                dp[0][i] = S.charAt(i) == T.charAt(0) ? i : -1;
        for (int j = 1; j < T.length(); ++j) {
                int last = -1;
                Arrays.fill(dp[j & 1], -1);
                for (int i = 0; i < S.length(); ++i) {
                        if (last >= 0 && S.charAt(i) == T.charAt(j))
                                dp[j & 1][i] = last;
                        if (dp[j & 1][i] >= 0)
                                last = dp[j & 1][i];
                }
        }
        int start = 0, end = S.length();
        for (int e = 0; e < S.length(); ++e) {
                int s = dp[T.length() & 1][e];
                if (s >= 0 && e - s < end - start) {
                        start = s;
                        end = e;
                }
        }
        return end < S.length() ? S.substring(start, end+1) : "";
}

x.
A naive brute force is relatively easy: for each starting position S[i], scan left to right trying to match elements T[j] in order. Unfortunately, this is

O(S^2)

complexity, so we seek to improve it.

Java: brute force, Time O(s*t), Space O(s*t)

public String minWindow(String S, String T) {
        int min = -1, idx = -1;
        char[] Tc = T.toCharArray();
        char[] Sc = S.toCharArray();
        for(int i = 0;i < S.length();i++){
                if(Sc[i] != Tc[0]) continue;
                int len = check(Tc,Sc,i);
                if(len <= 0) break;
                if(min == -1 || len < min){
                        idx = i;
                        min = len;
                }
        }
        if(min == -1) return "";
        return S.substring(idx, idx + min);
}
public int check(char[] Tc, char[] Sc, int start){
        int i = start, j = 0;
        while(i < Sc.length && j < Tc.length){
                if(Sc[i] == Tc[j]) j++;
                i++;
        }
        if(j == Tc.length) return i - start;
        return -1;
}

https://blog.csdn.net/zjucor/article/details/78511774

public String minWindow(String S, String T) {
char[] cs = S.toCharArray();
char[] ct = T.toCharArray();
int lo = T.length(), hi = S.length();
int min = Integer.MAX_VALUE, start = -1;
while(lo < hi) {
int mid = (lo+hi)/2;
int t = ok(cs, ct, mid);
if(t != -1) {
min = mid;
start = t;
hi = mid;
} else {
lo = mid+1;
}
}
return min==Integer.MAX_VALUE ? "" : S.substring(start, start+min);
}
private int ok(char[] cs, char[] ct, int mid) {
for(int i=0; i<cs.length-mid+1; i++) {
if(isSeq(cs, i, i+mid-1, ct))
return i;
}
return -1;
}
private boolean isSeq(char[] cs, int s, int t, char[] ct) {
int i = s, j = 0;
while(i <= t) {
while(i<=t && cs[i]!=ct[j]) i++;
if(i > t) break;
i++;
j++;
if(j == ct.length) return true;
}
return false;
}

LeetCode 727 - Minimum Window Subsequence

Labels

Popular Posts