Halo

A magic place for coding

0%

LeetCode解题报告（439）-- 727. Minimum Window Subsequence

Posted on Edited on Valine:

Problem

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 is a subsequence of the part.

If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

1
2
3
4
5
Input: s1 = "abcdebdde", s2 = "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 s2 in the window must occur in order.

Example 2:

1
2
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

Constraints:

  • 1 <= s1.length <= 2 * 104
  • 1 <= s2.length <= 100
  • s1 and s2 consist of lowercase English letters.

Analysis

  题目给出了两个字符串s1和s2，然后要求在s1中找到一个substring（连续的），使得s2是这个substring的subsequence。首先这种两个字符串的题目，又涉及到substring、subsequence，一般就可以往dp方面想了。通常来说是一个二维的dp，那么这里的方程怎么确定呢？还是按照老套路，dp[i][j]表示s1中前i个字符组成的substring能使得s2的前j个字符是sequence的初始位置。例如，s1 = dbd，s2 = bd，那么dp[2][1] = 1，因为在s1中起始下标是1。

  然后我们来看转移方程，如果s1[i] == s2[j]就很好办，因为不会影响起始位置，所以dp[i][j] = dp[i - 1][j - 1]；如果s1[i] != s2[j]，那么只能是s1向前找了，所以是dp[i - 1][j]。

  最后，因为答案要求的是返回s1中的substring，所以要记录初始位置以及最小的长度。

Solution

  无。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string minWindow(string s1, string s2) {
        int m = s1.size(), n = s2.size(), start = -1, minLen = INT_MAX;
        
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        
        for (int i = 0; i <= m; ++i) {
            dp[i][0] = i;
        }
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                dp[i][j] = (s1[i - 1] == s2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j]);
            }
            if (dp[i][n] != -1) {
                int len = i - dp[i][n];
                if (len < minLen) {
                    minLen = len;
                    start = dp[i][n];
                }
            }
        }
        return (start == -1) ? "": s1.substr(start, minLen);
    }
};

Summary

  这道题目是两个字符串dp的变种题目，难度在于要记录的是起始位置，同时状态转移也需要有一些思考。这道题目的分享到这里，感谢你的支持！

Welcome to my other publishing channels