Skip to content

Instantly share code, notes, and snippets.

@MicBrain
Created September 13, 2015 18:23
Show Gist options
  • Save MicBrain/75bf2338d72e937e9df0 to your computer and use it in GitHub Desktop.
Save MicBrain/75bf2338d72e937e9df0 to your computer and use it in GitHub Desktop.
/* Problem 1.1: Implement an algorithm to determine if a string
* has all unique characters. What if you cannot use additional
* data structures?
* @author: Rafayel Mkrtchyan
* @date: 9/13/2015
*/
#include <iostream>
#include <algorithm>
/* This solution uses an additional data structure -
* array of boolean values that has 256 elements.
* The speed of this solution is O(n).
*/
bool is_unique_usingMemory(std::string str) {
bool UniquenessChecker[256] = {false};
for (int index = 0; index < str.length(); index++) {
int value = str[index];
if (UniquenessChecker[value] == true) {
return false;
}
UniquenessChecker[value] = true;
}
return true;
}
/* This solution uses no additional data structures.
However, the speed of this one is O(NlogN).
*/
bool is_unique_noMemory(std::string str) {
std::sort(str.begin(), str.end());
for (int index = 0; index < str.length() - 1; index++) {
if (str[index] == str[index + 1]) {
return false;
}
}
return true;
}
int main () {
std::string str1 = "Berkeley";
bool first1 = is_unique_usingMemory(str1);
bool first2 = is_unique_noMemory(str1);
std::cout << first1 << " " << first2 << std::endl;
std::string str2 = "Stanford";
bool second1 = is_unique_usingMemory(str2);
bool second2 = is_unique_noMemory(str2);
std::cout << second1 << " " << second2 << std::endl;
std::string str3 = "Columbia";
bool third1 = is_unique_usingMemory(str3);
bool third2 = is_unique_usingMemory(str3);
std::cout << third1 << " " << third2 << std::endl;
std::string str4 = "Harvard";
bool fourth1 = is_unique_noMemory(str4);
bool fourth2 = is_unique_usingMemory(str4);
std::cout << fourth1 << " " << fourth2 << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment