If a String Has All Unique Characters

Description

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

Tips:

To address a more suitable solution, we should really confirm the scope of set, where those characters come from. Is it ASCII characters? or simply 26 letters? We probably will have different solution for these cases.

Suppose we have a set of ASCII characters. Then we could declare a boolean array of size 256. Each element in this array represents the appearing status of a specific character in the ASCII list. All of the elements are initially set to false which indicate that the character at corresponding position never appeared before, while true indicate that the character has appeared before.

Pseudo-code

1
2
3
4
5
6
7
8
9
10
11
12
13

declare a boolean array of size 256
for(char n in the string)
{
  if( n’s corresponding element in boolean array == true)
  //means it already appeared before
  {
      return false;
  }
  else
  {
      set it to true, and continue;
  }
}

My C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14

bool isUnique(string s)
{
    bool characterPool[256];
    memset(characterPool, false, sizeof(characterPool));
    size_t len = s.length();
    for (int n = 0; n < len; n++)
    {
        int index = (int)s[n];
        if (characterPool[index] == true) return false;
        else
            characterPool[index] = true;
    }
    return true;
}

My Objective-C Solution

Test the Solution

1
2
3
4
5
6
7

int main()
{
    string s1 = "ss";
    string s2 = "abcdefghijklmnopqrstuvwxyzABCD1234567890";
    cout << isUnique(s1) << " " << isUnique(s2) << endl;
    return 0;
}

Comments