给出两个字符串s和t,要求在s中找出最短的包含t中所有字符的连续子串
时间: 2024-03-10 22:47:33 浏览: 102
这是一个经典的字符串问题,可以使用滑动窗口(双指针)算法来解决。
具体做法如下:
1. 定义两个指针left和right,分别指向s的开头和结尾。
2. 定义一个哈希表need,用来存储t中每个字符出现的次数。
3. 定义一个哈希表window,用来存储当前窗口中每个字符出现的次数。
4. 初始化left=0,right=0,count=0,其中count表示当前窗口中已经包含了t中的字符个数。
5. 开始遍历字符串s,每次将right指针向右移动一位,同时更新window中相应字符的出现次数。
6. 如果当前字符是t中的字符,并且window中该字符出现次数不超过need中该字符的出现次数,则count加1。
7. 当count等于t中字符的总数时,表示当前窗口已经包含了t中所有字符,此时可以尝试移动left指针。
8. 移动left指针时,如果当前字符不是t中的字符,或者window中该字符的出现次数超过need中该字符的出现次数,则可以直接移动left指针。
9. 如果当前字符是t中的字符,并且window中该字符出现次数大于need中该字符的出现次数,则需要继续移动left指针,直到window中该字符出现次数不超过need中该字符的出现次数。
10. 在每次移动left指针时,更新最短子串的长度和起始位置。
11. 重复步骤5到10,直到right指针遍历完整个字符串s。
最后,如果存在符合条件的子串,则返回最短子串,否则返回空字符串。
示例代码如下:
```python
def min_window(s: str, t: str) -> str:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0) + 1
left = right = 0
count = 0
start = 0
min_len = float('inf')
for right in range(len(s)):
c = s[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] <= need[c]:
count += 1
while count == len(t):
if right - left + 1 < min_len:
start = left
min_len = right - left + 1
c = s[left]
if c in need:
window[c] -= 1
if window[c] < need[c]:
count -= 1
left += 1
return s[start:start+min_len] if min_len != float('inf') else ""
```
这个算法的时间复杂度是O(n),其中n是字符串s的长度,空间复杂度是O(m),其中m是字符串t中不同字符的个数。
阅读全文
相关推荐


















