確定是否字符串具有獨特的所有字符

「確定一個字符串擁有所有獨特字符假設你只能使用數組。」。

我有一個工作解決方案，但我想看看是否有任何更好的時間複雜度方面的優化。我不想使用LINQ。感謝您提供的任何幫助！

static void Main(string[] args) 
{ 
    FindDupes("crocodile"); 
} 

static string FindDupes(string text) 
{ 
    if (text.Length == 0 || text.Length > 256) 
    { 
     Console.WriteLine("String is either empty or too long"); 
    } 

    char[] str = new char[text.Length]; 
    char[] output = new char[text.Length]; 

    int strLength = 0; 
    int outputLength = 0; 

    foreach (char value in text) 
    { 
     bool dupe = false; 
     for (int i = 0; i < strLength; i++) 
     { 
      if (value == str[i]) 
      { 
       dupe = true; 
       break; 
      } 
     } 
     if (!dupe) 
     { 
      str[strLength] = value; 
      strLength++; 

      output[outputLength] = value; 
      outputLength++; 
     } 
    } 
    return new string(output, 0, outputLength); 
}

來源

2012-10-01 mynameisneo

這應該是在[codereview.stackexchange.com]（http://codereview.stackexchange.com） –

的開銷是，你沒有嵌套循環 - 通過迭代長度的字符串 - 而不是使用更簡單的IndexOf函數。提示：編碼時嘗試將事物想象成「抽象」。如果我要求你寫一個函數來計算每個人在這個線程中的年齡，你會怎麼稱呼這個方法？ 'SumAges（int [] ages）'或 - 從目的中抽象出功能並將其稱爲'Sum（int [] numbers）'。反之亦然，你會考慮對字符串進行嵌套循環操作，以檢查char是否在字符串中，而不是查找內置的BCL字符串方法嗎？ –

@DaveZych - 嗨戴夫，我不知道codereview.stackexchange.com。在SO和CR上發佈問題的協議是什麼？ – mynameisneo

如果時間複雜度是所有你關心你可以映射到int值的特點，然後有一個布爾值的數組它記住了你以前是否看過特定的字符值。

喜歡的東西... [沒有測試過]

bool[] array = new bool[256]; // or larger for Unicode 

foreach (char value in text) 
    if (array[(int)value]) 
    return false; 
    else 
    array[(int)value] = true; 

return true;

來源

2012-10-01 04:29:08

PS「確定一個字符串是否包含所有唯一字符」意味着布爾結果，而不是一串唯一字符或刪除重複項的字符串。 –

這是OP要求的最佳答案。你儘可能快地找到一個謎題，並且如果符號已經出現，用簡單的標誌進行靜態映射是你能做的最快速的檢查。編輯：@Ian即使...它很容易改變你的解決方案，只複製非重複字符到一個新的字符串。顯式算法仍然是最好的。不是一些花哨的單線。 PS：在if（array [（int）char）'中輸入錯字 - 缺少括號']'。 – luk32

上面的代碼有一些語法錯誤，無效的表達式字符'char'應該是'值' – chridam

試試這個，

string RemoveDuplicateChars(string key) 
    { 
     string table = string.Empty; 
     string result = string.Empty; 
     foreach (char value in key) 
     { 
      if (table.IndexOf(value) == -1) 
      { 
       table += value; 
       result += value; 
      } 
     } 
     return result; 
    }

使用

Console.WriteLine(RemoveDuplicateChars("hello")); 
Console.WriteLine(RemoveDuplicateChars("helo")); 
Console.WriteLine(RemoveDuplicateChars("Crocodile"));

輸出

helo 
helo 
Crocdile

來源

2012-10-01 04:10:33

可以請您建議兩個空白字符串的用法是什麼？我覺得表格或結果中的任何一個都足夠了。 –

@SteveWellens鱷魚爲什麼失敗？它有重複的字母'o'吧？ –

對於沒有LINQ的解決方案，爲+1 – Habib

public boolean ifUnique(String toCheck){ 
    String str=""; 
    for(int i=0;i<toCheck.length();i++) 
    { 
     if(str.contains(""+toCheck.charAt(i))) 
      return false; 
     str+=toCheck.charAt(i); 
    } 
    return true; 
}

編輯：

您也可以考慮省略邊界情況下toCheck是一個空字符串。

來源

2012-10-01 05:04:58

下面的代碼工作：

static void Main(string[] args) 
    { 
     isUniqueChart("text"); 
     Console.ReadKey(); 

    } 

    static Boolean isUniqueChart(string text) 
    { 
     if (text.Length == 0 || text.Length > 256) 
     { 
      Console.WriteLine(" The text is empty or too larg"); 
      return false; 
     } 
     Boolean[] char_set = new Boolean[256]; 
     for (int i = 0; i < text.Length; i++) 
     { 
      int val = text[i];//already found this char in the string 
      if (char_set[val]) 
      { 
       Console.WriteLine(" The text is not unique"); 
       return false; 
      } 
      char_set[val] = true; 
     } 
     Console.WriteLine(" The text is unique"); 
     return true; 
    }

來源

2013-04-09 20:01:30 AkxumiteEmpire

這假設字符限制爲255.超出此範圍的任何字符都將導致錯誤，如Â。爲什麼不使用字典？ –

如果字符串只有小寫字母（az）或只有大寫字母（AZ），你可以使用一個非常優化的O（1）solution.Also O（ 1）空間。

C++代碼：

bool checkUnique(string s){ 
    if(s.size() >26) 
     return false; 
    int unique=0; 
    for (int i = 0; i < s.size(); ++i) { 
     int j= s[i]-'a'; 
     if(unique & (1<<j)>0) 
      return false; 
     unique=unique|(1<<j); 
    } 
    return true; 
}

來源

2015-11-24 21:11:47

確定是否字符串具有獨特的所有字符

回答

相關問題