## Sunday, May 20, 2018

### 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.
1.     public String minWindow(String S, String T) {
2.         int[][] dp = new int[2][S.length()];
3.
4.         for (int i = 0; i < S.length(); ++i)
5.             dp[0][i] = S.charAt(i) == T.charAt(0) ? i : -1;
6.
7.         for (int j = 1; j < T.length(); ++j) {
8.             int last = -1;
9.             Arrays.fill(dp[j & 1], -1);
10.             for (int i = 0; i < S.length(); ++i) {
11.                 if (last >= 0 && S.charAt(i) == T.charAt(j))
12.                     dp[j & 1][i] = last;
13.                 if (dp[~j & 1][i] >= 0)
14.                     last = dp[~j & 1][i];
15.             }
16.         }
17.
18.         int start = 0, end = S.length();
19.         for (int e = 0; e < S.length(); ++e) {
20.             int s = dp[~T.length() & 1][e];
21.             if (s >= 0 && e - s < end - start) {
22.                 start = s;
23.                 end = e;
24.             }
25.         }
26.         return end < S.length() ? S.substring(start, end+1) : "";
27.     }
https://www.jianshu.com/p/beaa7079a0fb

    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

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， 返回最小的。如果没有返回 ""

    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
1.     public String minWindow(String S, String T) {
2.         char[] cs = S.toCharArray();
3.         char[] ct = T.toCharArray();
4.         int lo = T.length(), hi = S.length();
5.         int min = Integer.MAX_VALUE, start = -1;
6.
7.         while(lo < hi) {
8.             int mid = (lo+hi)/2;
9.             int t = ok(cs, ct, mid);
10.             if(t != -1) {
11.                 min = mid;
12.                 start = t;
13.                 hi = mid;
14.             } else {
15.                 lo = mid+1;
16.             }
17.         }
18.
19.         return min==Integer.MAX_VALUE ? "" : S.substring(start, start+min);
20.     }
21.
22.     private int ok(char[] cs, char[] ct, int mid) {
23.         for(int i=0; i<cs.length-mid+1; i++) {
24.             if(isSeq(cs, i, i+mid-1, ct))
25.                 return i;
26.         }
27.         return -1;
28.     }
29.
30.     private boolean isSeq(char[] cs, int s, int t, char[] ct) {
31.         int i = s, j = 0;
32.         while(i <= t) {
33.             while(i<=t && cs[i]!=ct[j])  i++;
34.             if(i > t) break;
35.             i++;
36.             j++;
37.             if(j == ct.length)  return true;
38.         }
39.         return false;
40.     }