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 | Input: s1 = "abcdebdde", s2 = "bde" |
Example 2:
1 | Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u" |
Constraints:
1 <= s1.length <= 2 * 104
1 <= s2.length <= 100
s1
ands2
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 | class Solution { |
Summary
这道题目是两个字符串dp的变种题目,难度在于要记录的是起始位置,同时状态转移也需要有一些思考。这道题目的分享到这里,感谢你的支持!