Created
March 1, 2014 04:04
-
-
Save vo/9284932 to your computer and use it in GitHub Desktop.
Different ways to check for duplicates in a string
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <map> | |
#include <algorithm> | |
#include <climits> | |
// using STL MAP | |
bool duplicate_check_maphist(std::string s) | |
{ | |
std::map<char, int> h; | |
for (int i = 0; i < s.length(); ++i) | |
if (h[s[i]] == 1) return true; | |
else h[s[i]] += 1; | |
return false; | |
} | |
// using an array to store histogram | |
bool duplicate_check_arrayhist(std::string s) | |
{ | |
int h[255]; | |
for(int i=0; i<255; h[i]=0, ++i); | |
for(int i=0; i<s.length(); ++i) | |
if (h[s[i]] == 1) return true; | |
else h[s[i]] += 1; | |
return false; | |
} | |
// check every pair of characters (O(n^2)) | |
bool duplicate_check_inplace(std::string s) | |
{ | |
size_t len = s.length(); | |
for(int i=0; i<len; ++i) | |
for(int j=i+1; j<len; ++j) | |
if(s[i] == s[j]) | |
return true; | |
return false; | |
} | |
// check using counting every possible char | |
// technically O(n), efficient for large strings | |
// (much larger than CHAR_MAX) | |
bool duplicate_check_inplace_count(std::string s) | |
{ | |
size_t len = s.length(); | |
for(int i=0; i<=CHAR_MAX; ++i) | |
if (std::count(s.begin(), s.end(), i) > 1) | |
return true; | |
return false; | |
} | |
// check by sorting the string and checking for consecutives | |
// this is kind of a cheap way of doing it. | |
bool duplicate_check_sort(std::string s) { | |
std::sort(s.begin(), s.end()); | |
std::string::iterator it = std::adjacent_find(s.begin(), s.end()); | |
return (it == s.end()) ? false : true; | |
} | |
int main() | |
{ | |
// ask user input | |
std::cout << "Enter a string: "; | |
std::string s; | |
std::getline(std::cin, s); | |
// check the length | |
bool has_duplicate = duplicate_check_maphist(s); | |
if (has_duplicate) | |
std::cout << "There is a duplicate!" << std::endl; | |
else | |
std::cout << "There are no duplicates!" << std::endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment