题目要求:给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
解题思路:
这是一道滑动窗口的题目,我们可以用两个指针 left 和 right 表示窗口的左右边界,用一个哈希表记录 T 中每个字符出现的次数,然后移动右指针,直到窗口中包含了 T 中所有字符,然后移动左指针,缩小窗口大小,直到窗口中不再包含 T 中所有字符,然后再移动右指针,扩大窗口大小,以此类推,直到右指针越界,得到最小子串。
具体实现可以用一个计数器 count 表示当前窗口中包含 T 中字符的个数,用一个变量 minLen 记录当前最小子串的长度,用两个变量 minLeft 和 minRight 记录当前最小子串的左右边界,用一个哈希表记录当前窗口中每个字符出现的次数。
算法步骤:
初始化 left、right 指针,哈希表、计数器 count 以及 minLeft、minRight 和 minLen。
移动 right 指针,扩大窗口,如果当前字符是 T 中的字符,更新哈希表和计数器 count。
当 count 等于 T 中字符的个数时,移动 left 指针,缩小窗口,如果当前字符是 T 中的字符,更新哈希表和计数器 count。
更新最小子串的长度和左右边界。
重复步骤 2、3、4,直到 right 指针越界。
返回最小子串。
领取专属 10元无门槛券
私享最新 技术干货