LeetCode30题求助：单词排列导致内存溢出（OOM）问题

我正在解决LeetCode第30题《串联所有单词的子串》，现有代码已完成大部分逻辑，当前代码通过DoPermutation方法生成所有单词的排列组合，再通过TrackIndexes匹配字符串中的子串，已通过151个测试用例，但在处理指定大输入时出现**内存溢出（Out of Memory）**错误。

问题出在DoPermutation生成的排列列表占用内存过大，导致OOM。想请教是否可以修改现有代码解决该问题，还是需要重新设计解题思路？

代码核心目标是生成单词的所有可能排列，并匹配模式字符串中的对应子串。

测试输入如下：

s = "pjzkrkevzztxductzzxmxsvwjkxpvukmfjywwetvfnujhweiybwvvsrfequzkhossmootkmyxgjgfordrpapjuunmqnxxdrqrfgkrsjqbszgiqlcfnrpjlcwdrvbumtotzylshdvccdmsqoadfrpsvnwpizlwszrtyclhgilklydbmfhuywotjmktnwrfvizvnmfvvqfiokkdprznnnjycttprkxpuykhmpchiksyucbmtabiqkisgbhxngmhezrrqvayfsxauampdpxtafniiwfvdufhtwajrbkxtjzqjnfocdhekumttuqwovfjrgulhekcpjszyynadxhnttgmnxkduqmmyhzfnjhducesctufqbumxbamalqudeibljgbspeotkgvddcwgxidaiqcvgwykhbysjzlzfbupkqunuqtraxrlptivshhbihtsigtpipguhbhctcvubnhqipncyxfjebdnjyetnlnvmuxhzsdahkrscewabejifmxombiamxvauuitoltyymsarqcuuoezcbqpdaprxmsrickwpgwpsoplhugbikbkotzrtqkscekkgwjycfnvwfgdzogjzjvpcvixnsqsxacfwndzvrwrycwxrcismdhqapoojegggkocyrdtkzmiekhxoppctytvphjynrhtcvxcobxbcjjivtfjiwmduhzjokkbctweqtigwfhzorjlkpuuliaipbtfldinyetoybvugevwvhhhweejogrghllsouipabfafcxnhukcbtmxzshoyyufjhzadhrelweszbfgwpkzlwxkogyogutscvuhcllphshivnoteztpxsaoaacgxyaztuixhunrowzljqfqrahosheukhahhbiaxqzfmmwcjxountkevsvpbzjnilwpoermxrtlfroqoclexxisrdhvfsindffslyekrzwzqkpeocilatftymodgztjgybtyheqgcpwogdcjlnlesefgvimwbxcbzvaibspdjnrpqtyeilkcspknyylbwndvkffmzuriilxagyerjptbgeqgebiaqnvdubrtxibhvakcyotkfonmseszhczapxdlauexehhaireihxsplgdgmxfvaevrbadbwjbdrkfbbjjkgcztkcbwagtcnrtqryuqixtzhaakjlurnumzyovawrcjiwabuwretmdamfkxrgqgcdgbrdbnugzecbgyxxdqmisaqcyjkqrntxqmdrczxbebemcblftxplafnyoxqimkhcykwamvdsxjezkpgdpvopddptdfbprjustquhlazkjfluxrzopqdstulybnqvyknrchbphcarknnhhovweaqawdyxsqsqahkepluypwrzjegqtdoxfgzdkydeoxvrfhxusrujnmjzqrrlxglcmkiykldbiasnhrjbjekystzilrwkzhontwmehrfsrzfaqrbbxncphbzuuxeteshyrveamjsfiaharkcqxefghgceeixkdgkuboupxnwhnfigpkwnqdvzlydpidcljmflbccarbiegsmweklwngvygbqpescpeichmfidgsjmkvkofvkuehsmkkbocgejoiqcnafvuokelwuqsgkyoekaroptuvekfvmtxtqshcwsztkrzwrpabqrrhnlerxjojemcxel", 
words = ["dhvf","sind","ffsl","yekr","zwzq","kpeo","cila","tfty","modg","ztjg","ybty","heqg","cpwo","gdcj","lnle","sefg","vimw","bxcb"]

1. 现有代码无法修复，必须重设计思路 #

生成全排列的思路在单词数量较多时（比如你的测试用例有18个单词），排列数是18!（约6.4×10¹⁵），这是天文数字，根本不可能在内存中存储，所以必须放弃生成全排列的暴力思路。

2. 优化方案：滑动窗口 + 哈希表统计 #

核心逻辑是利用题目中「所有单词长度相同」的特点，通过统计单词出现次数来匹配，而非生成排列：

• 先计算单个单词长度wordLen，总匹配长度totalLen = wordLen × words.Length，如果s长度小于totalLen直接返回空列表。
• 用哈希表wordCount统计words中每个单词的出现次数。
• 遍历s中所有可能的起始偏移（范围是0到wordLen-1，覆盖所有可能的起始位置）：
  • 维护滑动窗口，窗口长度固定为totalLen，用哈希表windowCount统计窗口内的单词出现次数。
  • 移动窗口时，移除左端的单词，添加右端的新单词，对比windowCount和wordCount是否完全一致，一致则记录当前窗口的起始索引。

3. 核心代码示例（C#） #

public List<int> FindSubstring(string s, string[] words)
{
    List<int> result = new List<int>();
    if (string.IsNullOrEmpty(s) || words == null || words.Length == 0)
        return result;

    int wordLen = words[0].Length;
    int totalLen = wordLen * words.Length;
    if (s.Length < totalLen)
        return result;

    Dictionary<string, int> wordCount = new Dictionary<string, int>();
    foreach (string word in words)
    {
        if (wordCount.ContainsKey(word))
            wordCount[word]++;
        else
            wordCount[word] = 1;
    }

    // 遍历所有可能的起始偏移
    for (int i = 0; i < wordLen; i++)
    {
        int left = i;
        int right = i;
        Dictionary<string, int> windowCount = new Dictionary<string, int>();
        int matched = 0;

        while (right + wordLen <= s.Length)
        {
            string currentWord = s.Substring(right, wordLen);
            right += wordLen;

            if (wordCount.ContainsKey(currentWord))
            {
                if (windowCount.ContainsKey(currentWord))
                    windowCount[currentWord]++;
                else
                    windowCount[currentWord] = 1;

                // 当前单词匹配次数达标
                if (windowCount[currentWord] == wordCount[currentWord])
                    matched++;

                // 当所有单词匹配次数都达标时，检查窗口长度
                while (matched == wordCount.Count)
                {
                    if (right - left == totalLen)
                        result.Add(left);

                    // 移动左边界，缩小窗口
                    string leftWord = s.Substring(left, wordLen);
                    left += wordLen;

                    if (wordCount.ContainsKey(leftWord))
                    {
                        if (windowCount[leftWord] == wordCount[leftWord])
                            matched--;
                        windowCount[leftWord]--;
                    }
                }
            }
            else
            {
                // 当前单词不在目标列表中，直接重置窗口
                windowCount.Clear();
                matched = 0;
                left = right;
            }
        }
    }

    return result;
}

为什么这个思路能解决OOM问题 #

该思路完全不生成任何排列，仅通过哈希表统计和滑动窗口移动完成匹配，内存占用仅与单词种类数相关，和单词数量的阶乘无关，彻底解决内存溢出问题，同时时间复杂度远低于暴力排列解法。

内容的提问来源于stack exchange，提问作者user8512043