これら2つの方法の複雑さをどのように減らすことができますか？

Question

は、私は、問題のパフォーマンスのベンチマークを満たしていない

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
class Solution 
{ 

    // returns true or false based on whether s1 and s2 are 
    // an unordered anagrammatic pair 
    // e.g. "aac","cac" --> false 
    //  "aac","aca" --> true 
    // Complexity: O(n) 
    static bool IsAnagrammaticPair(string s1, string s2) 
    { 
     if(s1.Length != s2.Length) 
      return false; 
     int[] counter1 = new int[26], 
       counter2 = new int[26]; 
     for(int i = 0; i < s1.Length; ++i) 
     { 
      counter1[(int)s1[i] - (int)'a'] += 1; 
      counter2[(int)s2[i] - (int)'a'] += 1; 
     } 
     for(int i = 0; i < 26; ++i) 
      if(counter1[i] != counter2[i]) 
       return false; 
     return true; 
    } 

    // gets all substrings of s (not including the empty string, 
    // including s itself) 
    // Complexity: O(n^2) 
    static IEnumerable<string> GetSubstrings(string s) 
    { 
     return from i in Enumerable.Range(0, s.Length) 
       from j in Enumerable.Range(0, s.Length - i + 1) 
       where j >= 1 
       select s.Substring(i, j); 
    } 

    // gets the number of anagrammatical pairs of substrings in s 
    // Complexity: O(n^2) 
    static int NumAnagrammaticalPairs(string s) 
    { 
     var substrings = GetSubstrings(s).ToList(); 
     var indices = Enumerable.Range(0, substrings.Count); 
     return (from i in indices 
       from j in indices 
       where i < j && IsAnagrammaticPair(substrings[i], substrings[j]) 
       select 1).Count(); 
    } 

    static void Main(String[] args) 
    { 
     int T = Int32.Parse(Console.ReadLine()); 
     for(int t = 0; t < T; ++t) 
     { 
      string line = Console.ReadLine(); 
      Console.WriteLine(NumAnagrammaticalPairs(line)); 
     } 
    } 
} 

のようないくつかのコードを持っています。 2つのヘルパー・メソッドは、私は、しかし、私は私が取得に関わる操作の数を減らすことができる方法を見ていない、私はコメントで述べたように、私はO(n^2)いることを知っている

GetSubstrings 

と

NumAnagrammaticalPairs 

を持っています回答。何か案は？

Answer 1

LINQを使用してアナガマティックペアをチェックできます。しかし、パフォーマンスについてはわかりません。

public class Program 
{ 
    public static void Main() 
    { 
     string x="aac"; 
     string y ="caa"; 

     List<char> lstX = x.ToCharArray().OrderBy(m=>m).ToList<char>(); 
     List<char> lstY =y.ToCharArray().OrderBy(m=>m).ToList<char>(); 


     Console.WriteLine(IsAnagramaticPair(x,y)); 
    } 

    public static bool IsAnagramaticPair(string x ,string y) 
    { 
     List<char> lstX = x.ToCharArray().OrderBy(m=>m).ToList<char>(); 
     List<char> lstY =y.ToCharArray().OrderBy(m=>m).ToList<char>(); 

     return lstX.SequenceEqual(lstY); 

    } 
} 

Answer 2

考えられる2つの可能性があります。まず、ソート両方の文字列と結果を比較：

static bool IsAnagrammaticPair(string s1, string s2) 
{ 
    var srt1 = s1.OrderBy(c => c); 
    var srt2 = s2.OrderBy(c => c); 
    return s1.SequenceEqual(s2); 
} 

メートルの場合、nは文字列の長さであり、それはO（N MログMログN +）です。

もう1つの可能性は、1つの文字列から文字のヒストグラムを作成し、次に他の文字列から文字と関連する数を比較することです。

static bool IsAnagrammaticPair(string s1, string s2) 
{ 
    if (s1.Length != s2.Length) return false; 

    var l1 = s1.ToLookup(c => c); 
    return s2.GroupBy(c => c).All(g => l1.Contains(g.Key) && l1[g.Key].Count() == g.Count()); 
} 

最初の部分のためのO（n）のだが、O（n）の余分なスペースを持つ：文字列は、しかしそれが機能するために同じ長さ、でなければなりません。そして2番目の部分はO（m）です。

Answer 3

各部分集合が同じ長さの文字列で構成されるように、部分文字列の部分集合を取ることができます。

その後、ソートO（n log n）を使用して文字列を直接比較することができます。

また、ソートを使用して、各サブセットを適切な順序で並べ替えることができます（ixj比較はありません）。

static void Main(string[] args) 
    { 
     int T = Int32.Parse(Console.ReadLine()); 
     for (int t = 0 ; t < T ; ++t) 
     { 
      string line = Console.ReadLine(); 
      Console.WriteLine(NumAnagrammaticalPairs(line)); 
     } 
    } 

    static int NumAnagrammaticalPairs(string s) 
    { 
     int sum = 0; 
     foreach (var substrings in GetSubstringsByLength(s)) 
     { 
      // Count for each string how many others are identical 
      int toSum = 0; 
      for (int i = 1 ; i < substrings.Count ; i++) 
       if (substrings[i - 1] == substrings[i]) 
       { 
        toSum++; 
        sum += toSum; 
       } 
       else 
       { 
        toSum = 0; 
       } 
     } 

     return sum; 
    } 

    static IEnumerable<List<string>> GetSubstringsByLength(string s) 
    { 
     for (int length = 1 ; length < s.Length ; length++) 
      yield return GetSubstringsOfLength(s, length); 
    } 

    static List<string> GetSubstringsOfLength(string s, int length) 
    { 
     var result = new List<string>(); 

     for (int i = 0 ; i <= s.Length - length ; i++) 
     { 
      var substring = s.Substring(i, length); 
      result.Add(new string(substring.OrderBy(c => c).ToArray<char>())); 
     } 

     result.Sort(); 

     return result; 
    }