如何減少這兩種方法的複雜性？

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)); 
     } 
    } 
} 

這是不符合問題的性能基準測試一些代碼。兩個輔助方法我有

GetSubstrings 

和

NumAnagrammaticalPairs 

我知道是O(n^2)我在評論中提到的，但是我不知道怎樣才能減少涉及檢索操作的數量回答。有任何想法嗎？

Answer 1

您可以使用LINQ來檢查anagarmatic對。不確定性能。

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

想到兩種可能性。首先，排序字符串和比較結果：

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

如果m和n是串的長度，那麼這是O（n日誌N + M日誌米）。

另一種可能性是從一個字符串中製作字符的直方圖，然後比較來自另一個字符串的字符和相關計數。該字符串必須爲工作相同的長度，但：

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）的額外空間。而O（m）爲第二部分。

Answer 3

您可以獲取子字符串的子集，以便每個子集由具有相同長度的字符串組成。

之後，您可以或使用排序O（n日誌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; 
    }