Halo

A magic place for coding

0%

LeetCode解题报告(439)-- 727. Minimum Window Subsequence

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

  题目给出了两个字符串s1s2,然后要求在s1中找到一个substring(连续的),使得s2是这个substring的subsequence。首先这种两个字符串的题目,又涉及到substring、subsequence,一般就可以往dp方面想了。通常来说是一个二维的dp,那么这里的方程怎么确定呢?还是按照老套路,dp[i][j]表示s1中前i个字符组成的substring能使得s2的前j个字符是sequence的初始位置。例如,s1 = dbds2 = 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