Determine if a string has unique characters

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.

Solution 1 (Use set ):

C++:
01 bool uniqueString(string s)
02 {
03     set <char> t;
04     for(int i=0;i<s.length();i++){
05         char c=s[i];
06         if(t.find(c)==t.end())
07             t.insert(c);
08         else
09             return false;
10     }
11     return true;
12 }

Solution 2(Use array):

C++:
01 bool uniqueString(string s)
02 {
03     bool t[256];
04     for(int i=0;i<256;i++)
05         t[i]=false;
06     for(int i=0;i<s.length();i++){
07         if(t[s[i]]==true)
08             return false;
09         else
10             t[s[i]]=true;
11     }
12 }

Solution 3 (Use bit vector):

C++:
01 bool uniqueString(string s)
02 {
03     int test=0;
04     for(int i=0;i<s.length();i++){
05         if(test>>(s[i]‘a’)&1==1)
06             return false;
07         else
08             test=test|1<<(s[i]‘a’);
09     }
10     return true;
11 }

The bit vector solution only works when the string is lower case only string.

If string has more character types other than lower case English characters and no additional data type is allowed, we can do the following:

1) Compare each pair of characters with O(n^2);

2) Sort the string according to the characters, check if there are duplicates.

Advertisements
This entry was posted in Array and linked list, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s