在包含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