-1

我有这个适用于较小输入的解决方案说输入字符串的长度可达 350，除此之外它会给出运行时错误。输入约束是 0 < input<500 。

这个问题来自https://www.hackerrank.com/contests/quantium/challenges/k-mismatch

如何优化此代码以处理长度为 500 的字符串？

语言 c#

  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Threading.Tasks;
  class Solution {
static int mismatch(string a, string b)
    {
        int result = 0;    
        for (int i = 0; i < a.Length; i++)
           if (a[i] != b[i])
               result++;
        return result;
    }
    static void Main(string[] args)
    {
        long no = 0;
        int K = int.Parse(Console.ReadLine());
        string word = Console.ReadLine();
        List<string> wordList = new List<string>();
        List<string> curr = new List<string>();

        var query =
             from i in Enumerable.Range(0, word.Length)
             from j in Enumerable.Range(0, word.Length - i + 1)
             where j >= 1
             select word.Substring(i, j);


        for (int i = 1; i < word.Length; i++)
        {
            foreach (string s in query) { if (s.ToString().Length == i)curr.Add(s);  }
            if (curr.Count() > 1) 
                for (int j = 0; j < curr.Count(); j++)
                    for (int k = j + 1; k < curr.Count(); k++)
                        if (mismatch(curr.ElementAt(j).ToString(),      curr.ElementAt(k).ToString()) <= K)
                        no++;
                curr.Clear();

        }
Console.WriteLine(word.Length+":"+no);

    }
}
4

1 回答 1

2

我在这里看到的主要限制因素是您正在计算特定字符串的每个子字符串，然后将整个查询具体化为一个列表（使用 line query.ToList();）。对于非平凡大小的字符串，这将消耗大量内存。不将其转换为列表而是对查询本身进行 foreach 将允许您流式传输该信息，从而大大减少您的内存占用。由于您对每个字母都进行了迭代，因此不实现它意味着将每个值计算 N 次，这将减慢程序的速度。既然你没有足够的内存，你别无选择，只能忍受这种减速（除非你可以改进底层算法，不需要多次执行如此大而复杂的查询）。

于 2013-08-09T17:53:36.537 回答