数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在Python中查找包含另一个字符串所有字符的最小窗口
假设我们有两个字符串s1和s2，我们需要找到s1中最小的子串，使得s2的所有字符都能被有效利用。
因此，如果输入类似于s1 = "I am a student"，s2 = "mdn"，则输出将是"m a studen"
为了解决这个问题，我们将遵循以下步骤：
N := 26
str_len := 主字符串的长度，patt_len := 模式的长度
如果 str_len < patt_len，则
返回 None
hash_pat := 一个大小为N的数组，并填充为0
hash_str := 一个大小为N的数组，并填充为0
对于 i 从 0 到 patt_len，执行
hash_pat[pattern[i] 的ASCII码] := hash_pat[pattern[i] 的ASCII码] + 1
start := 0, start_index := -1, min_len := 无穷大
count := 0
对于 j 从 0 到 str_len，执行
hash_str[main_str[j] 的ASCII码] := hash_str[main_str[j] 的ASCII码] + 1
如果 hash_pat[main_str[j] 的ASCII码] 不等于 0 并且 hash_str[main_str[j] 的ASCII码] <= hash_pat[main_str[j] 的ASCII码]，则
count := count + 1
如果 count 等于 patt_len，则
当 hash_str[main_str[start] 的ASCII码] > hash_pat[main_str[start] 的ASCII码] 或 hash_pat[main_str[start] 的ASCII码] 等于 0 时，执行
如果 hash_str[main_str[start] 的ASCII码] > hash_pat[main_str[start] 的ASCII码]，则
hash_str[main_str[start] 的ASCII码] := hash_str[main_str[start] 的ASCII码] - 1
start := start + 1
len_window := j - start + 1
如果 min_len > len_window，则
min_len := len_window
start_index := start
如果 start_index 等于 -1，则
返回 None
返回 main_str 的子串（从索引 start_index 到 start_index + min_len）
示例
让我们看看下面的实现，以便更好地理解：
N = 256
def get_pattern(main_str, pattern):
str_len = len(main_str)
patt_len = len(pattern)
if str_len < patt_len:
return None
hash_pat = [0] * N
hash_str = [0] * N
for i in range(0, patt_len):
hash_pat[ord(pattern[i])] += 1
start, start_index, min_len = 0, -1, float('inf')
count = 0
for j in range(0, str_len):
hash_str[ord(main_str[j])] += 1
if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
count += 1
if count == patt_len:
while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
hash_str[ord(main_str[start])] -= 1
start += 1
len_window = j - start + 1
if min_len > len_window:
min_len = len_window
start_index = start
if start_index == -1:
return None
return main_str[start_index : start_index + min_len]
main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))输入
"I am a student", "mdn"
输出
m a studen
397 次浏览
