Question

我在LeetCode尝试了一个问题,似乎几乎是这样。这就是我迄今为止所做的工作:Fiddle 和问题链接——30. Substring with Connation of Alls Words/。下面是我迄今为止所做的法典:

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"]

守则一在<代码> 单程式方法中列出了可能的改动清单,对于上述投入,该编码生成了从记忆错误中提取的示意图清单。我不敢肯定,如果能够用我所拥有的法典来改变任何东西。

现在,在180个测试案例中,我的代码为151个。是否在利用现行法典避开记忆例外,或者我必须重新思考这一问题?

<>>目标: 守则的主要目的是为护卫清单制定可能的调和,使之与按护卫模式标示的护卫相匹配。

Answer 1

您的问题是,你正在编制一份名单,列出您的言辞。然而,没有必要这样做。你们都需要做的是: 点数 ,以某种条件进行可能的下调和测试。可在C#中实施<代码>。 IE amountable<string []> methods that onlysils one string range at a time.

The following is one such, written against .NET 8 /C# 12:

public static class EnumerableExtensions
{
    ///<summary>
    ///Enumerate the possible permutations of the incoming array.  
    ///Note that the memory of the returned array is reused for the next permutation
    ///</summary>
    public static IEnumerable<T []> EnumeratePermutations<T>(this T [] array)
    {
        if (array.Length == 0)
        {
            yield return array;
            yield break;
        }
        
        // Mutate a copy rather than the original
        var copy = array.ToArray();
        
        static IEnumerable<T []> EnumeratePermutations(T [] array, int start)
        {
            if (start >= array.Length)
                throw new ArgumentException("start >= array.Length");
            for (int i = start; i < array.Length; i++)
            {
                Swap(ref array[start], ref array[i]);
                yield return array;
                Swap(ref array[start], ref array[i]);
            }
        }

        var stack = new Stack<IEnumerator<T []>>();
        try
        {
            stack.Push(EnumeratePermutations(copy, 0).GetEnumerator());
            while (stack.Count != 0)
            {
                var enumerator = stack.Peek();
                if (!enumerator.MoveNext())
                    stack.Pop().Dispose();
                else if (stack.Count < copy.Length)
                    stack.Push(EnumeratePermutations(enumerator.Current, stack.Count).GetEnumerator());
                else
                    yield return enumerator.Current;
            }
        }
        finally
        {
            foreach (var enumerator in stack)
                enumerator.Dispose();
        }
    }
    
    static void Swap<T>(ref T a, ref T b) 
    {
        var temp = a;
        a = b;
        b = temp;
    }
}

I chose to implement this with an explicit stack rather than with recursion for performance reasons, and to avoid potential stack overflows.

然后,您可修改<代码>TrackIndexes()以采用。 IE amountable<string []> aLst debate, and conducted as before:

static List<int> TrackIndexes(string pattern, IEnumerable<string []> aLst) {
  // TODO: write and test this yourself
}

That being said, while this will solve your out-of-memory problem, it won t pass 30. Substring with Concatenation of All Words. Simply generating every permutation then checking to see whether the concatenation is contained in the target string will take O(s.Length * Factorial(words.Length)) which won t be fast enough to pass the test. You re going to need to vastly cut down the number of permutations you enumerate by doing some quick rejects, or switch to an alternate approach as suggested by Glubus in their answer.

Answer 2

You got me to actually do the puzzle for funzies now. While your solution might work with some optimizations, I think you should step away from your current idea and rethink the problem. Try to re-explain the problem to yourself.

Hint:使用“变迁”一词是一种诱使你产生这一名单的诱骗。试图不作此用地表明问题。

Hint with minor spoilers

The way I solved it was using these method names and signatures:

<代码>公开 IList<int> FindSubstring (string s, string[]word)

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

<编码>bool 次级标准缩略语:

This solution is still very inefficient and is just my first approach without considering run time and memory usage too much. Probably there is more clever approaches still.

Hint with minor spoilers

友情链接