465. Optimal Account Balancing
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.
题意：找出一个 S 串中的字串且 T 是这个字串的 subsequence 且返回最短的字串长度。
解法1 可以用dp解来做，dp[i] 存放的是i元素之后离得最近的26个元素的index 不能包括i本身，因为像 “aa” 这种情况处理不了。 这个复杂度是 N * k的
class Solution {
public String minWindow(String s, String T) {
int len = s.length();
int[][] dp = new int[len][26];
for(int[] arr : dp) {
Arrays.fill(arr, -1);
}
dp[len - 2][s.charAt(len - 1) - 'a'] = len - 1;
for(int i = len - 3; i >= 0; i--) {
for(int j = 0; j < dp[0].length; j++) {
dp[i][j] = dp[i + 1][j] == -1 ? -1 : dp[i+1][j];
}
dp[i][s.charAt(i + 1) - 'a'] = i + 1;
}
int n = T.length();
int ret = Integer.MAX_VALUE;
int start = 0, end = 0;
for(int i = 0; i < len ; i++) {
if(s.charAt(i) == T.charAt(0)) {
int tmp = 1;
int cur = i;
for(int j = 1; j < n; j++) {
int next = T.charAt(j) - 'a';
if(dp[cur][next] == -1) {
tmp = -1;
break;
} else {
tmp += Math.abs(dp[cur][next] - cur);
cur = dp[cur][next];
}
}
if(tmp != -1 && tmp < ret) {
ret = tmp;
start = i;
end = tmp + i;
}
}
}
return s.substring(start, end);
}
}
解法2 用两个指针一直向前移动，如果发现当前元素子序列匹配成功，那么，我们可以向前在一一比较，即可以找出最短的那个。 重复这个操作即可。 这个先扩张在收缩的滑动窗口 复杂度为 (S * w)， w是回头匹配的长度。最差情况 w = s
class Solution {
public String minWindow(String s, String t) {
if(s.equals(t)) return t;
int start = 0, end = s.length() -1, ret = Integer.MAX_VALUE, retl = 0, retr = 0;
int i = 0, j = 0;
while(i < s.length()) {
char a = s.charAt(i);
char b = t.charAt(j);
if(a == b) {
j++;
i++;
} else {
i++;
}
if(j == t.length()) {
end = i;
j--;
i--;
while(j >= 0) {
if(s.charAt(i) == t.charAt(j)) {
i--;
j--;
} else {
i--;
}
}
start = i + 1;
i += 2;
if(end - start < ret) {
retl = start;
retr = end;
ret = end - start ;
}
j = 0;
}
}
return s.substring(retl, retr);
}
}