Проверьте строку на дубликат char

Question

первый раз я пишу на SO, потому что он не мог найти решение самостоятельно. На собеседовании мне была дана задача написать метод, который проверяет символы в строке на уникальный.

Требования:: не используется LINQ. Желаемое: не использовать дополнительные типы данных (словарь, HashSet ... и т.д. Массивы и списки Разрешенные.)

Пример:

"Hello" - return false; "Helo" - return true 

Моя реализация:

static HashSet<char> charSet = new HashSet<char>(); 

static bool IsUniqueChar(string str) 
{  
    foreach (char c in str) 
    {    
      charSet.Add(c);       
    } 
    return charSet.Count() == str.Length; 
} 

Но он не соответствует требованиям типов данных, и это не лучшая производительность ... Я также пробовал подходить со словарем:

static Dictionary<char,bool> charSetDictionary = new Dictionary<char,bool>(); 

static bool IsUniqueChar(string str) 
{ 
    try 
    { 
     foreach (char c in str) 
     { 
      charSetDictionary.Add(c,true); 
     } 
    } 
    catch 
    { 
     return false; 
    } 

Но он не лучше предыдущего. Я буду приветствовать любую идею, как решить эту задачу лучше? пс

static void Main(string[] args) 
{ 
    Stopwatch sw = Stopwatch.StartNew(); 

    IsUniqueChar("Hello"); 

    sw.Stop(); 

    Console.WriteLine("Elapsed={0}", sw.Elapsed); //~005044 
} 

Answer 1

Скорее всего, ваш интервьюер хотел бы видеть подход, используя знания о Unicode:

static bool[] charsHash = new bool[512]; 

static bool IsUniqueChar(string str) 
{ 
    if (str.Length > 512) return false; 

    foreach (char c in str) 
    { 
     bool alreadyExist = charsHash[(int)c]; 
     if (alreadyExist) return false; 
     else charsHash[(int)c] = !alreadyExist; 
    } 
    return true; 
} 

static void Main(string[] args) 
{ 
    Stopwatch sw = Stopwatch.StartNew(); 

    IsUniqueChar("Hello"); 

    sw.Stop(); 
    Console.WriteLine("Elapsed={0}", sw.Elapsed);//~000283 
} 

Answer 2

Самый быстрый способ использует HashSet<char>:

var set = new HashSet<char>(); 

foreach(var c in input) 
{ 
    if(!set.Add(c)) 
     return false; 
} 

return true; 

Это O (п) решение в худшем случае (вход уникален). Возвращает false, как только будет найден первый дубликат.

Без HashSet<char> вы можете легко преобразовать string в char[], сортировать его и проверить, есть ли у вас два последовательных элемента с одинаковым значением.

var chars = input.ToCharArray(); 
chars.Sort(); 

for(int i = 1; i < chars.Length; i++) 
{ 
    if(chars[i-1] == chars[i]) 
     return false; 
} 

return true; 

Sort является О (п log (п)) и так является целой функцией.

Answer 3

Пусть тест строка передается через textBox1, то из этого следует:

string tst; 
int i,j, stat =0; 
tst = textBox1.Text; 
for (i = 0; i < tst.Length; i++) 
{ 
    for (j = 0; j < tst.Length; j++) 
    { 
     if ((tst[i] == tst[j]) && (i != j)) 
     { 
      stat = 1; 
      break; 
     } 
     else continue; 
    } 
    if (stat == 1) break; 
    else continue; 
} 
if (stat == 1) MessageBox.Show("False"); 
else MessageBox.Show("True"); 

Каждая строка представляет собой массив символов.

Answer 4

Все ответы до сих пор основаны на предположении, что один .NET char соответствует одному Unicode символов. Это справедливо только для символов в Basic Multilingual Plane. Символы вне BMP кодируются с использованием char объектов (суррогатная пара).

Следующий код обрабатывает это особый случай:

HashSet<string> set = new HashSet<string>(); 

for (int i = 0; i < str.Length; i++) 
{ 
    string s; 
    if (char.IsHighSurrogate(str[i])) 
    { 
     s = str.Substring(i, 2); 
     i++; 
    } 
    else 
    { 
     s = str.Substring(i, 1); 
    } 

    if (!set.Add(s)) 
    { 
     return false; 
    } 
} 
return true;