Tuesday, January 20, 2015

Algorithm to determine if a string has all unique characters

// Program to determine if a given string is unique.

#include <iostream>
#include <string>
using namespace std;

bool is_unique(string str) {
 if (str.length() > 256)  // assuming ASCII string (requires 256 bits storage)
  return false;

 bool a[256] = { false };  // create an array of 256 elements, initialize to false

 for(int k = 0; k < str.length(); k++) {  
  int ascii_val = int(str[k]); // get the ascii val of char

  if (a[ascii_val] == true) // chk the ascii_val index of array a.
   return false;  // if it is true, it means we have already
      // seen this char, so return false

  a[ascii_val] = true;    // otherwise set it to true to mark it as
            // a char we have seen already
 }

 return true;
}

int main() {
 string test0 = "";
 string test1 = "Michael";
 string test2 = "Jackson";
 string test3 = "Hello World";
 string test4 = "Australia";
 
 bool a = is_unique(test0);
 bool b = is_unique(test1);
 bool c = is_unique(test2);
 bool d = is_unique(test3);
 bool e = is_unique(test4);

 cout << test0 << " is " << a << endl;
 cout << test1 << " is " << b << endl;
 cout << test2 << " is " << c << endl;
 cout << test3 << " is " << d << endl;
 cout << test4 << " is " << e << endl;

 return 0;
}

No comments:

Post a Comment