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

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) 中对字符串进行快速排序或合并排序，然后对已排序的字符串进行一次遍历以确定 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++ 库）。

Answer 3

您必须使用哈希表（或哈希集）来获得 O(n) 复杂度。以下实现使用按位运算，其中每个位对应于字母表中的每个字符。

/**
* Works for 0-127 ASCII string. Assuming, int is 16 bit.
**/
int isduplicate(const char* str){
    int hash[8]={0,0,0,0,0,0,0,0};
    while(*str){ 
        int pos=*str;
        if(hash[pos/16]&(1<<(pos%16)))
            return 1;
        hash[pos/16]|=(1<<(pos%16)); 
        str++;
    }
    return 0;
}

Answer 4

// ASCII assumed over unicode
// O(n) algorithm
// O(1) space
bool isUnique(string s) {
    // cannot exceed number of unique characters
    if (s.length() > 256) return false;
    bool checker[256];
    for (int i = 0; i < s.length(); i++) {
        int val = s.at(i);
        if (checker[val] == true)
            return false;
        checker[val] = true;
    }
    return true;
}