确定字符串是否具有所有唯一字符

Question

如何在不使用数组的情况下执行此操作？我有这个实现,但我需要不使用数组,位操作和任何其他C/C++库.

bool IsCharDuplication(string s) {
  bool result = false;
  bool controlArray[256];
  for (int i = 0; i < s.length(); i++) {
    int val = s[i];
    if (controlArray[val] == true) {
      result = true;
      break;
    }
    controlArray[val] = true;
  }
  return result;
}

Answer 1

使用两个嵌套循环:

bool IsCharDuplication(string s)
{   
 for (int i = 0; i < s.length(); i++) 
    for (int j = i+1; j < s.length(); j++) 
      if (s[i] == s[j])
        return true;   
 return false;
}

注意:你的算法的时间为O(N),但我的解决方案的时间为O(N ^ 2).

Answer 2

您可以比其他答案中建议的O(N ^ 2)算法做得更好.

例如,可以快速排序或合并排序在O(NlogN)String和比做在排序字符串单程,以确定是否有在O(N)的任何重复.总时间复杂度将为O(NlogN).

bool IsCharDuplication (string s)
{
  string s2 = sort(s);
  for (int i = 0; i < s.length () - 1; i++)
    if (s2[i] == s2[i+1])
      return true;
  return false;
}

我没有包含用于对字符串进行排序的代码,但是您可以轻松地找到这样的代码并编写自己的sort方法(因为您不允许使用C/C++库).