Определение, имеет ли строка все уникальные символы

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), вы должны использовать хеш-таблицу (или хэш-набор). Следующая импликация использует побитовые операции, где каждый бит соответствует каждому символу в алфавите.

/** 
* 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 3

Вы можете сделать лучше, чем алгоритм 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 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; 
}