本题是经典的“最小覆盖子串”问题,适用 滑动窗口 + 计数 的思想。核心做法如下:
need 统计字符串 t 中每个字符需要的数量(只含英文字母,用 ASCII 足够)。[left, right] 表示当前窗口,并维护变量 missing 表示还缺多少个字符(按出现次数计),初始为 |t|。right 扩张窗口:将 s[right] 对应的 need 计数减一;若减完后该字符的 need 仍 ≥ 0,说明它满足了 t 的部分需求,missing--。missing == 0 时,说明当前窗口已经覆盖了 t 的所有字符,此时尝试收缩左端 left,在仍满足覆盖条件下尽量缩短长度,并记录当前最短答案。一旦收缩到去掉 s[left] 会使 need[s[left]] > 0,表明覆盖被破坏,停止收缩并继续扩张右端。给定字符串 s 与字符串 t,请在 s 中找出包含 t 中所有字符(含出现次数) 的最短子串并输出该子串。
若 s 中不存在这样的子串,输出空字符串 ""(不带引号)。
注:对
t中重复字符,子串中对应字符的数量必须不少于t中该字符的数量。若存在解,保证答案唯一。
st"",不包含引号。输入:
ADOBECODEBANC
ABC
输出:
BANC
输入:
a
a
输出:
a
输入:
a
aa
输出:
s与t由英文字母组成本题属于以下题库,请选择所需题库进行购买