-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

ここで見られる主な制限要因は、特定の文字列のすべての部分文字列を計算し、そのクエリ全体をリストに具体化するという事実です (行でquery.ToList();)。これは、自明でないサイズの文字列に対して大量のメモリを消費します。それをリストに変換せず、代わりにクエリ自体を foreach することで、その情報をストリーミングできるため、メモリ使用量を大幅に削減できます。ただし、文字ごとに反復するため、具体化しないと、これらの値をそれぞれ N 回計算することになり、プログラムの速度が低下します。あなたが持っていないのでただし、その速度低下に耐えるしかない十分なメモリがあります（そのような大規模で複雑なクエリを何度も実行する必要がないように、基礎となるアルゴリズムを改善できない限り）。

于 2013-08-09T17:53:36.537 に答える