c# - 检查重复字符上的字符串

Question

我第一次在SO上写，因为他自己找不到解决方案。在面试中，我的任务是编写一个方法来检查字符串中的字符是否唯一。

要求:不使用 LINQ。 理想:不要使用额外的数据类型(字典、哈希集等。数组和列表允许)

示例:

"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

最快的方法是使用 HashSet<char> :

var set = new HashSet<char>();

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

return true;

这是最坏情况下的O(n) 解决方案(输入是唯一的)。返回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是 O(n log(n)) 整个函数也是。