力扣题解 #8

📝

内容提要

给定两个字符串 s 和 t，返回 s 的最小窗口子串，使得 t 中每个字符都在其中。若无此子串，返回空字符串。方法包括：检查 t 是否比 s 长，初始化两个大小为 256 的数组记录 t 中字符出现次数。遍历 s，更新字符计数，匹配所有字符后缩小窗口，更新最小长度并返回结果。

🎯

关键要点

• 给定两个字符串 s 和 t，返回 s 的最小窗口子串，使得 t 中每个字符都在其中。

• 如果 t 的长度大于 s，返回空字符串。

• 初始化两个大小为 256 的数组，记录 t 中字符出现次数。

• 遍历 s，更新字符计数，检查是否所有字符都匹配。

• 缩小窗口，更新最小长度，并返回结果。

❓

延伸问答

如何找到字符串 s 的最小窗口子串？

通过检查字符串 t 的字符出现次数，并在字符串 s 中更新字符计数，找到包含 t 中所有字符的最小窗口子串。

如果字符串 t 的长度大于字符串 s，会发生什么？

如果 t 的长度大于 s，则返回空字符串。

在实现最小窗口子串的算法时需要哪些数据结构？

需要两个大小为 256 的数组来记录字符串 t 和 s 中字符的出现次数。

如何判断当前窗口是否包含所有字符？

通过比较当前窗口中字符的计数与字符串 t 中字符的计数，检查是否所有字符都匹配。

在算法中如何缩小窗口？

通过从左侧开始缩小窗口，直到无法再维持 t 中所有字符的匹配。

返回的结果是什么？

返回找到的最小窗口子串，如果没有找到，则返回空字符串。

🏷️

标签

字符串 字符计数 最小窗口子串 窗口缩小