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 #1, 指针
找到一个匹配之后,以结尾为起始点,倒退着往前找。这样找到的是在[i, j]里最短的符合要求的substring。最坏结果是找到跟原来一摸一样的。
O(m * n) time. 对Complexity的需要研究一下
ref: https://leetcode.com/problems/minimum-window-subsequence/discuss/109356/JAVA-two-pointer-solution-(12ms-beat-100)-with-explaination
class Solution { public String minWindow(String s, String t) { int si = 0, ti = 0; String rt = s + "123"; while (si < s.length()) { if (s.charAt(si) == t.charAt(ti)) { if (ti == t.length() - 1) { int end = si; while (ti >= 0) { while (s.charAt(si) != t.charAt(ti)) { si--; } ti--; si--; } si++; if (rt.length() > end - si + 1) { rt = s.substring(si, end + 1); } } ti++; } si++; } return rt.equals(s + "123") ? "" : rt; } }
Solution #2, DP
dp[i][j] = k, i为T的index,j为S的index,k为以[0,i],[0,j]这2段substring最小的起点在s上
如果s[j] == t[i], dp[i][j]那可以借用dp[i - 1][j - 1]时的起点
如果s[j] != t[i],可以借用dp[i][j - 1]
注意dp的初始赋值
class Solution { public String minWindow(String s, String t) { int n = s.length(), m = t.length(); int[][] dp = new int[m][n]; for (int i = 0; i < n; i++) { if (s.charAt(i) == t.charAt(0)) dp[0][i] = i; else if (i > 0) dp[0][i] = dp[0][i - 1]; else dp[0][i] = -1; } for (int i = 1; i < m; i++) { dp[i][0] = -1; } for (int i = 1; i < m; i++) { for (int j = 1 ; j < n; j++) { if (i > j) dp[i][j] = -1; else { if (t.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i - 1][j - 1]; }else { dp[i][j] = dp[i][j - 1]; } } } } int min = n; String rt = ""; for (int i = 0; i < n; i++) { if (dp[m - 1][i] == -1) continue; if (min > i - dp[m - 1][i] + 1) { rt = s.substring(dp[m - 1][i], i + 1); min = i - dp[m - 1][i] + 1; } } return rt; } }
No comments:
Post a Comment