Skip to content

Instantly share code, notes, and snippets.

@anowell
Created October 23, 2012 08:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anowell/3937652 to your computer and use it in GitHub Desktop.
Save anowell/3937652 to your computer and use it in GitHub Desktop.
hasSameCharacters simple O(n) solution
// Expected behavior:
// 'abc', 'cba' => true
// 'abca', 'cba' => true
// 'cba', 'abca' => true
// '', '' => true
// 'abcd', 'abc' => false
// 'abc', 'abcd' => false
bool hasSameCharacters(char* c1, char* c2)
{
// returning false was how we decided to handle invalid input
if(c1==NULL || c2==NULL) {
return false;
}
// char has 256 values, so we track characters found in these arrays
bool bc1[256] = {0};
bool bc2[256] = {0};
for(int i=0; c1[i] != '\0'; ++i) {
int offset = c1[i];
bc1[offset] = true;
}
for(int i=0; c2[i] != '\0'; ++i) {
int offset = c2[i];
bc2[offset] = true;
}
for(int i=0; i<256; ++i) {
if(bc1[i] != bc2[i]) {
return false;
}
}
return true;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment