最小覆盖子串。给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。
示例:
1 |
|
说明:
- 如果 S 中不存这样的子串,则返回空字符串
""
。 - 如果 S 中存在这样的子串,我们保证它是唯一的答案。
思路一
首先统计目标串中每个字符的数目,以及整个目标串的长度,通过两个指针 i,j
指示包含目标串的字符串窗口的左右,将 j
向右移动,寻找满足条件的窗口,然后再向右移动 i
,查看更小的窗口:
1 |
|
时间复杂度 \(O(n)\)。
1 |
|
最小覆盖子串。给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。
示例:
1 |
|
说明:
""
。首先统计目标串中每个字符的数目,以及整个目标串的长度,通过两个指针 i,j
指示包含目标串的字符串窗口的左右,将 j
向右移动,寻找满足条件的窗口,然后再向右移动 i
,查看更小的窗口:
1 |
|
时间复杂度 \(O(n)\)。
1 |
|
微信打赏
支付宝打赏