Determine if a string has all unique characters (c++)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

/****************************************************************************************** ******************************************************************************************* Chapter 1 Arrays and Strings * Implement an algorithm to determine if a string has all unique characters. * What if you cannot use additional data structures? By: Hamed Kiani (July 14, 2015) ****************************************************************************************** ******************************************************************************************/ #include<iostream> using namespace std; // method 1: // using bit shifting, time: O(n), space: O(1) // only for string in [a-z], 28 chars // 1 (int) is a 4 bytes (32 bits) to count the presence of 28 chars // challenge: how to re-write this function to work for all 256 ASCII chars?? bool string_unique_bit(char *str) { int check = 0; int i = 0; // counter over the string // '/0' indicates the end of a c-string while(str[i] != '\0') { // (int) str[i]: cast the char to int; (int)'a' = 97 int pos = (int) str[i] - 'a'; // (1 << pos) shifts the bit representation of 1 (32 bits) to left by pos-steps // if ((check & (1 << pos)) >0 ) means that current char was seen before if ((check & (1 << pos)) >0 ) return false; // keeping the presence of each char in check check |= (1 << pos); // process the next char i++; } return true; } // method 2: // using an aditional buffer to keep the history of each seen char // time: O(n), space: O(n) // works for all ASCII chars: 0-255 // challenge: how to write this function without using i? bool string_unique(char * str) { // check is a bool array of 256, initialized as false bool check[256] = {false}; int i = 0; while(str[i] != '\0') { if (check[(int) str[i]]) // current char was seen before, return false; else { check[(int) str[i]] = true; i++; } } } // Test it! int main() { char * str; str = "hamed"; bool check; check = string_unique(str); if (check) cout << str << " has all unique chars" << endl; else cout << str << " does not have unique chars" << endl; return 0; }