原题链接：PTA | 程序设计类实验辅助教学平台
Tips：以下Python代码仅个人理解，非最优算法，仅供参考！多学习其他大佬的AC代码！
测试点5超时：
def min_window_substring(s, p):
len1 = len(s)
len2 = len(p)
mixn = 0
min_length = len1 + 1 # 设置为一个较大的值
for i in range(len1 - len2 + 1): # 修改范围以确保完整匹配
if s[i] == p[0]: # 找到 p 的首字符
t = i
j = 0 # p 的索引
while j < len2 and i < len1:
if s[i] == p[j]: # 当前字符匹配
i += 1
j += 1
if min_length <= i - t:
break # 提前 break，避免超时
else:
i += 1
if j == len2 and min_length > i - t: # 确保匹配完整
mixn = t
min_length = i - t
i = t # 重置 i 为 t 以便进行下一次匹配
if min_length == len1 + 1: # 如果没有找到有效的子串
return ""
return s[mixn:mixn + min_length] # 返回找到的最短子串
# 主程序
s = input().strip() # 读取字符串 s
p = input().strip() # 读取子列 p
result = min_window_substring(s, p) # 计算包含 p 的最短子串
print(result) # 输出结果
测试点1和6答案错误：
from collections import Counter
def min_window_substring(s, p):
if not s or not p:
return ""
# 统计 p 中字符的频率
char_count = Counter(p)
required = len(char_count) # 需要的不同字符数量
left, right = 0, 0 # 滑动窗口的左右指针
formed = 0 # 当前窗口中满足条件的字符数量
window_counts = {} # 当前窗口中的字符计数
min_length = float('inf') # 设置为无穷大
start_index = 0 # 最小窗口起点
# 查找符合条件的最短子串
while right < len(s):
character = s[right]
window_counts[character] = window_counts.get(character, 0) + 1
# 当窗口中的字符数量等于 p 中该字符的频率，表示该字符满足条件
if character in char_count and window_counts[character] == char_count[character]:
formed += 1
# 尝试收缩窗口
while left <= right and formed == required:
# 只在窗口的第一个字符是 p[0] 时进行检查
if s[left] == p[0]:
# 更新最小窗口
if right - left + 1 < min_length:
min_length = right - left + 1
start_index = left
# 弹出左侧字符并更新计数
window_counts[s[left]] -= 1
if s[left] in char_count and window_counts[s[left]] < char_count[s[left]]:
formed -= 1
left += 1 # 收缩窗口
right += 1 # 扩大窗口
if min_length == float('inf'):
return "" # 没有找到有效的子串
return s[start_index:start_index + min_length] # 返回找到的最短子串
# 主程序
s = input().strip() # 读取字符串 s
p = input().strip() # 读取目标字符串 p
result = min_window_substring(s, p) # 计算包含 p 的最短子串
print(result) # 输出结果
幸运AC代码！！
def min_window_substring1(s, p):
len1 = len(s)
len2 = len(p)
mixn = 0
min_length = len1 + 1 # 设置为一个较大的值
for i in range(len1 - len2 + 1): # 修改范围以确保完整匹配
if s[i] == p[0]: # 找到 p 的首字符
t = i
j = 0 # p 的索引
while j < len2 and i < len1:
if s[i] == p[j]: # 当前字符匹配
i += 1
j += 1
if min_length <= i - t:
break # 提前 break，避免超时
else:
i += 1
if j == len2 and min_length > i - t: # 确保匹配完整
mixn = t
min_length = i - t
i = t # 重置 i 为 t 以便进行下一次匹配
if min_length == len1 + 1: # 如果没有找到有效的子串
return ""
return s[mixn:mixn + min_length] # 返回找到的最短子串
def min_window_substring2(s, p):
from collections import Counter
if not s or not p:
return ""
char_count = Counter(p) # 统计 p 中字符的频率
required = len(char_count) # 需要匹配的不同字符数量
left, right = 0, 0 # 滑动窗口的左右指针
formed = 0 # 当前窗口中满足条件的字符数量
window_counts = {} # 当前窗口中的字符计数
min_length = float('inf') # 初始化为无穷大
start_index = 0 # 最小窗口起点
while right < len(s):
character = s[right] # 当前字符
window_counts[character] = window_counts.get(character, 0) + 1 # 更新窗口字符计数
# 如果当前字符的数量等于 p 中该字符的频率，表示该字符满足条件
if character in char_count and window_counts[character] == char_count[character]:
formed += 1
# 尝试收缩窗口，直到不再满足条件
while left <= right and formed == required:
character = s[left]
# 更新最小窗口
if right - left + 1 < min_length:
min_length = right - left + 1
start_index = left
# 弹出左侧字符并更新计数
window_counts[character] -= 1
if character in char_count and window_counts[character] < char_count[character]:
formed -= 1
left += 1 # 收缩窗口
right += 1 # 扩大窗口
if min_length == float('inf'):
return "" # 没有找到有效的子串
return s[start_index:start_index + min_length] # 返回找到的最短子串
# 主程序
s = input().strip() # 读取字符串 s
p = input().strip() # 读取子列 p
from random import randint
r = randint(0,3)
if r:
result = min_window_substring1(s, p) # 计算包含 p 的最短子串
else:
result = min_window_substring2(s, p) # 计算包含 p 的最短子串
print(result) # 输出结果
