在包含Python中另一个字符串的所有字符的字符串中找到最小的窗口
假设我们有两个字符串s1和s2，我们必须在s1中找到最小的子字符串，这样才能有效地使用s2的所有字符。
因此，如果输入像s1=“我是学生”，s2=“mdn”，则输出将是“mastuden”
为了解决这个问题，我们将遵循以下步骤-
N：=26
str_len：=main_str的大小，patt_len：=模式的大小
如果str_len<patt_len，则
不返回
hash_pat：=大小为N的数组，并用0填充
hash_str：=大小为N的数组，并用0填充
对于范围在0到patt_len之间的我，执行
hash_pat[（（pattern[i]）的ASCII码]：=1
开始：=0，start_index：=-1，min_len：=inf
计数：=0
对于范围0到str_len的j，执行
而hash_str[（main_str[start]）的ASCII]>hash_pat[（main_str[start]）的ASCII]或hash_pat[（main_str[start]）的ASCII]与0相同，
len_window：=j-开始+1
如果min_len>len_window，则
hash_str[（main_str[start]）的ASCII]：=hash_str[（main_str[start]）的ASCII]-1
如果hash_str[（main_str[start]）的ASCII]>hash_pat[（main_str[start]）的ASCII]，则
开始：=开始+1
min_len：=len_window
start_index：=开始
数：=数+1
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]，则
如果计数与patt_len相同，则
如果start_index与-1相同，则
不返回
返回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