我正在研究Leetcode"最小窗口子字符串"练习问题：
给定两个字符串
s和长度分别为m和nt，返回s的最小窗口子字符串，以便t中的每个字符(包括重复字符)都包含在窗口中。如果没有这样的子字符串，则返回空字符串 "。将生成测试用例，以便答案是唯一的。
示例 1：
输入： s = "ADOBECODEBANC"， t = "ABC">
输出："BANC">示例 2：
输入： s = "a">， t = "a">
输出："a">例3：
输入：s = "a"， t = "aa">
输出：">
说明：t的两个'a'都必须包含在窗口中。由于s的最大窗口只有一个'a'，因此返回空字符串。
我的解决方案使用两个映射来跟踪字符计数：
strr映射是保持窗口中的字符数和patt映射适用于给定的模式字符串。
它还使用两个索引，start和end，来跟踪当前窗口(包括end)。
该解决方案的核心是一个推进end的外循环，将新字符添加到strr。然后，只要窗口有效，它就会运行内部循环：
- 检查并更新迄今为止看到的最短窗口
- 删除窗口中的第一个字符
- 推进
start.
一旦外部循环完成，它遇到的最短窗口应该是答案。
#include <iostream>
#include <unordered_map>
bool check_map(std::unordered_map<char, int> patt, std::unordered_map<char, int> strr)
{
for(auto data:patt)
{
if(strr[data.first] != data.second)
return false;
}
return true;
}
std::string Substring(std::string s, std::string t)
{
std::unordered_map<char, int> patt;
std::unordered_map<char, int> strr;
std::string ans;
for(int i=0; i<t.length(); i++)
patt[t[i]]++;
int start = 0, length = INT_MAX;;
for(int end=0; end<s.length(); end++)
{
strr[s[end]]++;
while(check_map(patt, strr))
{
if(length > (end-start+1))
{
ans = s.substr(start, end+1);
length = end-start+1;
}
strr[s[start]]--;
if(strr[s[start]] == 0)
strr.erase(s[start]);
start++;
}
}
return ans;
}
int main()
{
std::string s = "ADOBECODEBANC",
pattern = "ABC";
std::cout << "String: " << s << std::endl
<< "Pattern: " << pattern << std::endl
<< "Minimum Window Substring is " << Substring(s, pattern) << std::endl;
return 0;
}
例如问题中的 1，程序应返回"BANC"，而是返回"ADOBEC"。程序输出：
字符串：ADOBECODEBANC 模式：ABC 最小窗口子字符串是 ADOBEC
我的代码中的错误在哪里？
很抱歉，我无法回答您的具体问题"我的代码中的错误在哪里"。
但我能做的，就是帮助你理解问题，开发一个算法，并展示，众多潜在的解决方案之一。
问题的标题已经暗示了应该使用什么算法：所谓的"滑动窗口"算法。
你会在这里找到赛义德·斯里赫尼的一个很好的解释。
对于您的问题，我们将使用灵活尺寸滑动窗口方法。
我们将逐个字符迭代源字符串并等待，直到我们满足某个条件。在这种情况下，直到我们"看到"所有需要搜索的字符。然后，我们将找到一个窗口，所有这些字符都在其中。
在给定的示例中，滑动窗口的末尾始终是源字符串中最后一个读取字符。这是因为最后一个读取字符满足条件。然后我们需要找到窗口的开头。在这种情况下，源字符串中最右边的字符(搜索字符)的位置仍满足条件。
然后我们将继续读取源字符串并等待下一个条件得到满足。然后我们将重新计算滑动窗口位置。
顺便一提。除了源字符串中的搜索字符外，其他字符只是干扰，只会扩展滑动窗口的宽度。
但是我们如何满足条件呢？
特别是，由于搜索字符的顺序无关紧要，而且，其中甚至可以有双字符？
解决方案是我们将"计数"。
首先，我们将计算搜索字符串中所有字符的出现次数。此外，我们将使用第二个计数器来指示是否所有字符都匹配。
然后，在迭代源字符串时，我们将递减我们看到的任何字符的计数器。如果搜索字符的计数达到 0，那么我们将递减"匹配"计数器。而且，如果为 0，则我们找到了所有搜索字符并且满足条件。然后我们可以计算窗口位置。
请注意：我们只会递减匹配计数器，如果在减少字符计数器后，该计数器将为 0。
示例(我将省略带有"x"es的噪音)：
- 搜索字符串"ABC"，源字符串："xxAxxxxBBBxCAxx"。 初始字符计数器将为 1,1,1
- ，匹配计数器将为 3。
- 阅读第一个"A"。计数器： 0,1,1 2
- 阅读第一个"B"。计数器： 0,0,1 1
- 阅读第二个"B"。计数器：0，-1,1 1(仅当字符计数器达到 0 时，我们才会减少匹配计数器)。
- 阅读第 3 个"B"。计数器：0，-2,1 1(仅当字符计数器达到 0 时，我们才会减少匹配计数器)。
- 阅读第一个"C"。计数器： 0，-2,0 0.匹配计数器为 0，满足条件。
请注意。负字符数表示更右边有更多的相同字符。
接下来，由于现在满足条件，我们将检查滑动窗口的位置。结束位置很清晰。这是源字符串中的最后一个读取字符。这导致了条件的满足。所以，很容易。
要获取滑动窗口的起始位置，我们将从源字符串的开头进行检查，在那里我们可以找到搜索字符。我们将增加其计数，如果计数大于 0，我们将再次增加匹配计数。如果匹配计数大于 0，我们找到了一个起始位置。现在的计数器： 1，-2,0 1
开始位置将在下一次检查时递增。我们永远不会从 0 重新开始，而只会从上次使用的起始位置开始。
好的，找到开始和结束位置后，我们有了第一个窗口，并将寻找潜在的较小窗口。我们将继续读取源字符串并检查
- 计算完滑动窗口位置后，计数器将为：1，-2,0 1
- 阅读下一个"A"。计数器： 0，-2,0 0.同样，条件得到满足。
- 我们继续滑动窗口检测。最后一个起始位置指向第一个"A"之后的字符"x">
- 递增起始位置并跳过所有"x"。继续
- 阅读第一个"B"。计数器： 0，-1,0 0
- 阅读第二个"B"。计数器： 0,0,0 0
- 阅读 3d 'B'。计数器： 0,1,0 1.窗口位置计算完成。起始位置是第三个 B。这个窗口比前一个窗口小，所以拿走它。
由于使用了源字符串，因此我们完成了并找到了解决方案。
如何实现这一点。我们将对计数器进行一个小抽象，并将其打包到一个迷你类中。这将封装字符和匹配计数的内部处理，并且可以在以后进行优化。
适用于所有类型的字符类型的计数器可以实现如下：
struct SpecialCounterForGeneralChar {
std::unordered_map<char, int> individualLetter{};
int necessaryMatches{};
SpecialCounterForGeneralChar(const std::string& searchLetters) {
for (const char c : searchLetters) individualLetter[c]++;
necessaryMatches = individualLetter.size();
}
inline void incrementFor(const char c) {
individualLetter[c]++;
if (individualLetter[c] > 0)
++necessaryMatches;
}
inline void decrementFor(const char c) {
individualLetter[c]--;
if (individualLetter[c] == 0)
--necessaryMatches;
}
inline bool allLettersMatched() { return necessaryMatches == 0; }
};
如果我们更多地了解输入数据，例如它仅限于 8 位字符，我们还可以使用：
struct SpecialCounter {
char individualLetter[256]{};
int necessaryMatches{};
SpecialCounter(const std::string& searchLetters) {
for (const char c : searchLetters) {
if (individualLetter[c] == 0) ++necessaryMatches;
individualLetter[c]++;
}
}
inline void incrementFor(const char c) {
individualLetter[c]++;
if (individualLetter[c] > 0)
++necessaryMatches;
}
inline void decrementFor(const char c) {
individualLetter[c]--;
if (individualLetter[c] == 0)
--necessaryMatches;
}
inline bool allLettersMatched() { return necessaryMatches == 0; }
};
这将比上述略快(在给定的限制下)
然后，程序的其余部分将只有 15 行代码。
这里的重要信息是，在我们开始实现第一行代码之前，我们需要思考很长时间。
一个好的算法和设计，将帮助我们找到一个最佳解决方案。
请参阅下面的完整示例解决方案：
#include <string>
#include <iostream>
#include <unordered_map>
#include <limits>
using Index = unsigned int;
// We want to hide the implementation of the special counter to the outside world
struct SpecialCounter {
char individualLetter[256]{};
int necessaryMatches{};
SpecialCounter(const std::string& searchLetters) {
for (const char c : searchLetters) {
if (individualLetter[c] == 0) ++necessaryMatches;
individualLetter[c]++;
}
}
inline void incrementFor(const char c) {
individualLetter[c]++;
if (individualLetter[c] > 0)
++necessaryMatches;
}
inline void decrementFor(const char c) {
individualLetter[c]--;
if (individualLetter[c] == 0)
--necessaryMatches;
}
inline bool allLettersMatched() { return necessaryMatches == 0; }
};
std::string solution(std::string toBeSearchedIn, std::string toBeSearchedFor) {
// Counter with somespecial properties
SpecialCounter counter(toBeSearchedFor);
// This will be slided. End of window is always last read character. Start of window may increase
Index currentWindowStart {};
// The potential solution
Index resultingWindowStart {};
Index resultingWindowWith{ std::numeric_limits<size_t>::max() };
// Iterate over all characters of the string under evaluation
for (Index index{}; index < toBeSearchedIn.length(); ++index) {
// We saw a character. So, subtract from characters to be searched
counter.decrementFor(toBeSearchedIn[index]);
// If we hit and found all necessary characters and adjusted the sliding windows start position
while (counter.allLettersMatched()) {
// Calculate start and width of sliding window. So, if we found a new, more narrow window
const unsigned int currentWindowWith{ index - currentWindowStart + 1 };
if (currentWindowWith < resultingWindowWith) {
// Remember one potential solution
resultingWindowWith = currentWindowWith;
resultingWindowStart = currentWindowStart;
}
// Now, for the sliding window. We saw and decremented thsi character before
// Now we see it in the sliding window and increment it again.
counter.incrementFor(toBeSearchedIn[currentWindowStart]);
// Slide start of window to one to the right
currentWindowStart++;
}
}
return (resultingWindowWith != std::numeric_limits<size_t>::max()) ? toBeSearchedIn.substr(resultingWindowStart, resultingWindowWith) : "No solution";
}
int main()
{
const std::string toBeSearchedIn{ "KKKADOBECODEBBBAANCKKK" };
const std::string toBeSearchedFor = { "AABBC" };
std::cout << "Solution:n" << solution(toBeSearchedIn, toBeSearchedFor) << 'n';
}
由于该问题是尝试练习的一部分，因此此答案不会为激发它的练习问题提供完整的解决方案。相反，它将按照要求执行：它将指出已发布代码的主要问题，以及如何发现它。
代码检查
一个巧妙的方法是检查需求、设计和实现之间的不匹配;巧妙的是因为这种方法与其说是一门科学，不如说是一门艺术，你很容易让自己误入歧途。这基本上涉及在头脑中运行设计和实现，就好像你是处理器一样，尽管可能一次只检查代码的一小部分。
一些实现看起来不错，例如：end在外部循环中前进，检查较小的窗口(并替换以前的最小窗口)。有些可以经得起更仔细的检查，例如在检查窗口是否有效后从窗口直方图中删除条目(对于算法的正确性，考虑良好的循环不变量非常有用，例如"窗口应始终有效"，并确保它们始终为真)。
但是，当您查看check_map时，存在不匹配。一个问题要求是：
t中的每个字符(包括重复字符)都包含在窗口中
虽然措辞有轻微的歧义(如果t中的字符出现在窗口中的次数多于t，窗口是否有效？)，但此要求的直接解读是s中的字符计数必须至少是t中的字符计数。在check_map中，计数被精确地比较。这强烈表明这是一个更仔细检查的地方。
测试
一种可以捕获各种错误的半自动化、系统化方法是使用测试，包括单元和集成(搜索本网站和整个网络将解释这些术语)。测试的一个关键部分是确定要测试的边缘情况。例如，如果您尝试使用搜索字符串"ACBA"和模式"AB"，则示例程序会正确找到最小窗口"BA"。但是，对于搜索字符串"ACBBA"，它返回"ACB"作为最小窗口。这表明该实现存在字符计数问题，这使得check_map成为主要嫌疑人(以及更新strr次要嫌疑人的行)。
对于另一个测试，请考虑搜索字符串"A123B12345A12BA123A"和模式"AAB"。这有 3 个潜在窗口，中间最短的。如果修复check_map并针对此测试用例测试代码，则代码将返回"A12BA123A"，而不是"A12BA"。这表明测试窗口有效性(再次check_map)或设置答案时存在问题。一些脚手架代码(例如打印start，end和更新时的ans)将揭示原因。
调试
可以揭示实现正确性问题的最通用方法是使用交互式调试器。对于示例代码，可以在各个关键点(如循环和分支的开头)设置断点。此外，您还可以在代码应该查找新窗口时在索引处使这些断点成为条件断点。如果这样做，您会发现check_map在您希望它返回true的情况下返回false。从那里，您可以开始介入check_map以观察它为什么要这样做。
修复后，代码仍然存在问题，尽管您需要一个测试用例，例如上面带有"A123B12345A12BA123A"的测试用例，因为"ADOBECODEBANC"测试用例的问题并不明显。逐步完成内部循环并检查各种变量将揭示出了什么问题。
检查接口
Bug基本上都有一个原因：你期望代码做一件事，但它做一些不同的事情。其中一个原因是误解了 API，因此阅读 API 文档以确保您的理解正确可能会有所帮助。通常，在转到 API 之前，您需要查找行为不符合您理解的特定 API 调用，调试可以揭示这些调用。我之所以提到这一点，是因为示例代码中有一个不正确的 API 调用。
结论
上述每种方法都会导致相同的错误：check_map中的比较。给定合适的测试用例，其中两个也可能导致额外的错误。
附加说明
效率
Substring不仅检查和跟踪t中的那些角色，而且检查和跟踪所有角色。这导致内部循环体被执行(包括更新ans)s中的每个字符，而不仅仅是模式中存在的字符。通常，您应该使实现正确，然后使其高效。但是，在这种情况下，Substring忽略不在模式中且更接近问题描述的字符是微不足道的。
类型
这个答案的早期表述，解决了这个问题的早期表述，涵盖了检查类型以检查它们是否最合适。对于更新的问题，这不再会导致错误发现。
早期表述中的一点仍然适用于设计解决方案。
从概念上讲，模式字符和当前窗口中的字符最合适的数据类型是多集。随着窗口的移动，可以简单地在多集中添加和删除字符。当前窗口的有效性是一个简单的子集运算(pattern ⊆ window)。但是，STL 中的multiset与数学多重集不对应。