Как уменьшить пространство сложность «isUniqueString»

Question

я написал следующее isUniqueCharsInString

public static bool isUniqueCharsInString(String str) 
     { 
      int[] charsCount = new int[256]; 
      for (int i = 0; i < charsCount.Length; i++) 
      { 
       charsCount[i] = 0; 
      } 
      for (int i = 0; i < str.Length; i++) 
      { 
       int val = str[i]; 
       charsCount[val] = charsCount[val] + 1; 
       if (charsCount[val] > 1) 
       { 
        return false; 
       } 

      } 
      return true; 

     } 

Хотя он работал well.How я мог уменьшить ее сложность, так что минимальный объем памяти может быть использован во время выполнения. С уважением.

Answer 1

Чтобы минимизировать сложность использования пространства byte[] или bool для вашего charsCount или даже лучше BitArray, так как только вы используете его для установки флагов:

public static bool isUniqueCharsInString(String str) 
{ 
    var charsCount = new BitArray(256); 
    for (int i = 0; i < str.Length; i++) 
    { 
     int val = str[i]; 
     if (charsCount[val]) 
     { 
      return false; 
     } 
     charsCount[val] = true; 
    } 
    return true; 
} 

Интересный альтернативный подход с использованием LINQ:

public static bool isUniqueCharsInString1(String str) 
{ 
    return str.ToCharArray().GroupBy(c => c).All(g => g.Count() <= 1); 
} 

Он менее оптимизирован как в пространстве, так и во времени, но гораздо более кратким и понятным.

Из-за любопытства: почему вас так беспокоит сложность пространства? В исходной реализации используется только массив размером 1 КБ (256 * 4 В).