字符串列表内存不足

Question

我正在尝试 LeetCode 中的一个问题，看起来快完成了。这就是我到目前为止所做的：Fiddle 和问题链接 - 30。所有单词串联的子字符串。以下是我到目前为止所做的代码片段：

static IList < int > FindSubstring(string s, string[] words) {
    var list = new List < IList < string >> ();
    DoPermutation(words, 0, words.Length - 1, list);

    return TrackIndexes(s, list);
  }

  static IList < IList < string >> DoPermutation(string[] str, int start, int end, IList < IList < string >> list) {
    if (start == end) {
      list.Add(new List < string > (str));
    } else {
      for (var i = start; i <= end; i++) {
        Swap(ref str[start], ref str[i]);

        DoPermutation(str, start + 1, end, list);

        Swap(ref str[start], ref str[i]);
      }
    }

    return list;
  }

  static void Swap(ref string a, ref string b) {
    var temp = a;
    a = b;
    b = temp;
  }

  static List < int > TrackIndexes(string pattern, IList < IList < string >> aLst) {
    int count = 0;

    List < string > strings;
    List < int > indexes = new List < int > ();

    foreach(var item in aLst) {
      string str = "";

      strings = new List < string > {
        String.Concat(item)
      };

      foreach(var list in item) {
        str += list;

        if (str.Length == strings[0].Length && pattern.Contains(str)) {
          indexes.AddRange(AllIndexesOf(pattern, str));
          count += 1;
        }
      }
    }

    indexes.Sort();
    return indexes.Distinct().ToList();
  }

public static int[] AllIndexesOf(string str, string substr, bool ignoreCase = false) 
{
  if (string.IsNullOrWhiteSpace(str) || string.IsNullOrWhiteSpace(substr)) 
  {
    throw new ArgumentException("String or substring is not specified.");
  }

  var indexes = new List<int>();
  int index = 0;

  while ((index = str.IndexOf(substr, index, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)) != -1) 
  {
    indexes.Add(index++);
  }

  return indexes.ToArray();
}

我遇到的问题是以下输入：

s = "pjzkrkevzztxductzzxmxsvwjkxpvukmfjywwetvfnujhweiybwvvsrfequzkhossmootkmyxgjgfordrpapjuunmqnxxdrqrfgkrsjqbszgiqlcfnrpjlcwdrvbumtotzylshdvccdmsqoadfrpsvnwpizlwszrtyclhgilklydbmfhuywotjmktnwrfvizvnmfvvqfiokkdprznnnjycttprkxpuykhmpchiksyucbmtabiqkisgbhxngmhezrrqvayfsxauampdpxtafniiwfvdufhtwajrbkxtjzqjnfocdhekumttuqwovfjrgulhekcpjszyynadxhnttgmnxkduqmmyhzfnjhducesctufqbumxbamalqudeibljgbspeotkgvddcwgxidaiqcvgwykhbysjzlzfbupkqunuqtraxrlptivshhbihtsigtpipguhbhctcvubnhqipncyxfjebdnjyetnlnvmuxhzsdahkrscewabejifmxombiamxvauuitoltyymsarqcuuoezcbqpdaprxmsrickwpgwpsoplhugbikbkotzrtqkscekkgwjycfnvwfgdzogjzjvpcvixnsqsxacfwndzvrwrycwxrcismdhqapoojegggkocyrdtkzmiekhxoppctytvphjynrhtcvxcobxbcjjivtfjiwmduhzjokkbctweqtigwfhzorjlkpuuliaipbtfldinyetoybvugevwvhhhweejogrghllsouipabfafcxnhukcbtmxzshoyyufjhzadhrelweszbfgwpkzlwxkogyogutscvuhcllphshivnoteztpxsaoaacgxyaztuixhunrowzljqfqrahosheukhahhbiaxqzfmmwcjxountkevsvpbzjnilwpoermxrtlfroqoclexxisrdhvfsindffslyekrzwzqkpeocilatftymodgztjgybtyheqgcpwogdcjlnlesefgvimwbxcbzvaibspdjnrpqtyeilkcspknyylbwndvkffmzuriilxagyerjptbgeqgebiaqnvdubrtxibhvakcyotkfonmseszhczapxdlauexehhaireihxsplgdgmxfvaevrbadbwjbdrkfbbjjkgcztkcbwagtcnrtqryuqixtzhaakjlurnumzyovawrcjiwabuwretmdamfkxrgqgcdgbrdbnugzecbgyxxdqmisaqcyjkqrntxqmdrczxbebemcblftxplafnyoxqimkhcykwamvdsxjezkpgdpvopddptdfbprjustquhlazkjfluxrzopqdstulybnqvyknrchbphcarknnhhovweaqawdyxsqsqahkepluypwrzjegqtdoxfgzdkydeoxvrfhxusrujnmjzqrrlxglcmkiykldbiasnhrjbjekystzilrwkzhontwmehrfsrzfaqrbbxncphbzuuxeteshyrveamjsfiaharkcqxefghgceeixkdgkuboupxnwhnfigpkwnqdvzlydpidcljmflbccarbiegsmweklwngvygbqpescpeichmfidgsjmkvkofvkuehsmkkbocgejoiqcnafvuokelwuqsgkyoekaroptuvekfvmtxtqshcwsztkrzwrpabqrrhnlerxjojemcxel", 

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

我的代码在

DoPermutation

方法中创建了一个可能的排列列表，对于上述输入，它生成了一个出现内存不足错误的字符串列表。我不确定是否可以使用我拥有的代码片段来更改任何内容。

目前，我的代码通过了 180 个测试用例中的 151 个。无论如何，是否可以使用现有的代码片段来消除内存异常，或者我必须重新考虑该问题？

目标：代码的主要目标是为字符串列表创建可能的排列，并将模式中的这些字符串作为子字符串进行匹配。

Answer 1

你现在让我真正开始做有趣的拼图了。 虽然您的解决方案可能可以进行一些优化，但我认为您应该放弃当前的想法并重新思考问题。 尝试向自己重新解释问题。

提示：“排列”一词的使用是一种诱饵，让您生成此列表。尝试在不使用这种用法的情况下表达问题。

有轻微剧透提示

我解决这个问题的方法是使用这些方法名称和签名：

public IList<int> FindSubstring(string s, string[] words)

Dictionary<string, int> ExtractWordOccurances(string candidateSubstring, int chopSize)

bool SubStringMeetsRequirements(Dictionary<string, int> extractedChunks, string[] words)

我有点贪婪在这里的内存使用，它可以进一步优化，但它的 CPU 效率很高。

如果您需要进一步的提示，请私信我，将我的解决方案放在这里感觉很糟糕。