Created
January 9, 2016 18:05
-
-
Save sdebnath/f5e5ac98c4c275bb0178 to your computer and use it in GitHub Desktop.
Determine if string contains all unique characters using a bitmap
This file contains 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 <stdio.h> | |
#include <string.h> | |
int is_unique(char* str) { | |
/* | |
* Bit check array for 256 values | |
* Rationale: 256 / 32 = 8. 32 for 32 bits in an integer | |
*/ | |
int check[8] = {0}; | |
int i, val, idx1, idx2; | |
int tmp; | |
for (i = 0; i < strlen(str); i++) { | |
/* | |
* To determine which bit is related to the val, | |
* we first divide the value by 8 to locate which "integer" * in the array of 8 we are dealing with | |
*/ | |
val = (int)str[i]; | |
idx1 = val / 32; | |
/* | |
* Once the first level map is located, now we need to | |
* determine which index in that integer corresponds to | |
* the value we are dealing with. We do by using the | |
* modulo operator: divide and get remainder, in this case | |
* divide by 32 since we have 32 bits in an integer | |
*/ | |
idx2 = val % 32; | |
tmp = check[idx1]; | |
if (tmp & (1 << idx2)) { | |
/* If we found a match, return immediately */ | |
return 0; | |
} else { | |
/* | |
* If we didn't find a match, preare a fresh | |
* integer with the one bit set to where we need it. | |
* Then use the 'or' operator to set it in the map | |
*/ | |
tmp |= (1 << idx2); | |
check[idx1] = tmp; | |
} | |
} | |
return 1; | |
} | |
int main() { | |
char *str1 = "abcdefgh"; | |
printf(">> str1: %d\n", is_unique(str1)); | |
char *str2 = "ello"; | |
printf(">> str2: %d\n", is_unique(str2)); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment