确定字符串是否包含所有唯一字符

Question

我正在研究一个算法问题集,它提出了以下问题:

"确定字符串是否包含所有唯一字符.假设您只能使用数组".

我有一个有效的解决方案,但我想看看是否有更好的时间复杂度优化.我不想使用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);
}

Answer 1

如果您关心时间复杂度,您可以将字符映射到int值,然后有一个bool值数组,它们会记住您之前是否看过特定的字符值.

有点像...... [未经测试]

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;