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

Search

    Table of Contents