LC 727. Minimum Window Subsequence 【lock，hard】

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].

Runtime: 44 ms, faster than 73.35% of C++ online submissions for Minimum Window Subsequence.

网上的DP解法。dp定义是能够匹配T[0,i]的最大的S的index.

举个例子，S = babad, T = bad,

i = 0时，只有当j=0，两个相等，所以此时dp = [0, -1, -1]

然后，dp = [0,1,-1]，然后, dp = [2, 1, -1], -> dp[2,2,-1] -> dp[2,2,2]

因为时从后往前更新，只有当T的每一个字符都匹配了才能把最开头的index传递到最后。中间即使有些匹配到，如果没有全部匹配也传递不了。

比如 S = babd, T = bad,

dp = [-1,-1,-1] -> dp[0,-1,-1] -> dp[0,1,-1] -> dp[2,1,-1] -> dp[2,1,1] 结果还是1.

class Solution {

public:

    string minWindow(string S, string T) {

        vector<int> dp(T.length(), -);

        string ans = "";

        for (int i = ; i < S.length(); i++) {

            for (int j = T.length() - ; j >= ; j--) {

                if (S[i] == T[j]) {

                    if (j == ) dp[j] = i;

                    else dp[j] = dp[j - ];

                }

            }

            int init = dp[T.length() - ];

            if (init != - && (ans == "" || i - init +  < ans.size())) {

                ans = S.substr(init, i - init + );

            }

        }

        return ans;

    }

};

这题还有双指针法，过段时间更新。

巴特西

LC 727. Minimum Window Subsequence 【lock，hard】

最新文章

热门文章