确定是否字符串具有独特的所有字符

“确定一个字符串拥有所有独特字符假设你只能使用数组。”。

我有一个工作解决方案，但我想看看是否有任何更好的时间复杂度方面的优化。我不想使用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

确定是否字符串具有独特的所有字符

回答

相关问题