determine if a string has all unique characters?

Can anybody tell me how to implement a program to check a string contains all uniqu开发者_如何转开发e chars ?

If you are talking about an ASCII string:

1. Create an int array [0-255], one for each character index, initialised to zero.

2. Loop through each character in the string and increment the respective array position for that character

3. If the array position already contains a 1, then that character has already been encountered. Result => Not unique.

4. If you reach the end of the string with no occurrence of (3), Result => the string is unique.

Sort the characters in the string using your algorithm of choice (e.g. the builtin qsort function), then scan the string checking for consecutive repeating letters; if you get to the end without finding any, the string contains all unique characters.

An alternative may be using some structure that has one bucket for each character the string may contain, all initialized to zero; you scan the string, incrementing the value of the bucket corresponding to the current character. If you get to increment a bucket that already has a 1 inside it you are sure that your string contains duplicates.

This can work fine with chars and an array (of size UCHAR_MAX+1), but it quickly gets out of hand when you start to deal with wide characters. In such case you would need a hashtable or some other "serious" container.

The best algorithm depends on the length of the strings to examine, the size of each character, the speed of the sorting algorithm and the cost of allocating/using the structure to hold the character frequencies.

Make a set of the letters, and count the values.

set("adoihgoiaheg") = set(['a', 'e', 'd', 'g', 'i', 'h', 'o']):

def hasUniqueLetters(str):
    return (len(set(str)) == len(str))

>>> hasUniqueLetters("adoihgoiaheg")
False

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

bool isUnique(string _str)
{
        bool char_set[256];
        int len = _str.length();

        memset(char_set, '\0', 256);
        for(int i = 0; i < len; ++i)
        {
            int val = _str[i]- '0';
            if(char_set[val])
            {
                return false;
            }
            char_set[val] = true;
        }

        return true;
    }

    int main()
    {
        cout<<"Value: "<<isUnique("abcd")<<endl;
        return 0;
    }

Use a 256-entry array. Fill it with 0. Now traverse the string setting the corresponding entry in the array to 1 if it's 0. Otherwise, there are repeated chars in the string.

Set an array of booleans of size equal to the character set to false. (Constant time). Scan the string; for each character, inspect the array at the characater's slot; if true, string has duplicate characters. If false, set that slot to true and continue. If you get to the end without encountering a duplicate, there aren't any and the string only contains unique characters. Running time: O(n) when n is the lenght of the string, with a pretty small constant.

Similarly (and without arrays), use a HASH TABLE!

//psuedo code:

1. go through each char of the string
2. hash the char and look it up in the hash table
3. if the table has the hash, return FALSE // since it's not unique
4. __else store the hash
5. return to step #1 until you're done

Run time is O(n) and memory space is better too since you don't need an array of 256 (asciis)

#include <stdio.h>

#define ARR_SIZE 32

unsigned char charFlag[ARR_SIZE];

void initFlag() {
    int i = 0;

    for (i = 0; i < ARR_SIZE; i++)
        charFlag[i] = 0;

}

int getFlag(int position) {
    int val = 0;
    int flagMask = 1;

    int byteIndex = position / 8;
    int locPos = position % 8;

    flagMask = flagMask << locPos;
//  flagMask = ~flagMask;

    val = charFlag[byteIndex] & flagMask;
    val = !(!val);
//  printf("\nhex: %x\n", val);
    return val;

}

void setFlag(int position) {
    int flagMask = 1;
    int byteIndex = position / 8;
    int locPos = position % 8;

    flagMask = flagMask << locPos;
    charFlag[byteIndex] = charFlag[byteIndex] | flagMask;

}
int isUniq(char *str) {
    int is_uniq = 1;

    do {
        char *lStr = str;
        int strLen = 0;
        int i;

        if (str == 0)
            break;

        while (*lStr != 0) {
            lStr++;
            strLen++;
        }

        initFlag();
        lStr = str;
        for (i = 0; i < strLen; i++) {
            if (getFlag(lStr[i]))
                break;

            setFlag(lStr[i]);
        }

        if (i != strLen)
            is_uniq = 0;

    } while (0);

    return is_uniq;
}

int main() {

    char *p = "abcdefe";
    printf("Uniq: %d\n", isUniq(p));
    return 0;
}

Use a HashTable, add the key for each character along with the count of occurrences as the value. Loop through the HashTable keys to see if you encountered a count > 1. If so, output false.

Simple solution will be using 2 loops. No additional data structure is needed to keep a track on characters.

bool has_unique_char(char *str,int n)
{
      if(n==0)
           return true;

      for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                    if(str[i] == str[j])
                          return false;
            }      
      }
      return true;
}

bool isUnique(char st[],int size)
{
    bool char_set[256]=false;
    for(int i=0;i<size;i++)
    {
        if(char_set[st[i]]-'0')
        return false;
        char_set[st[i]-'0')=true;
    }
    return true;
}

my original answer was also doing the similar array technique and count the character occurrence.

but i was doing it in C and I think it can be simple using some pointer manipulation and get rid of the array totally

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void main (int argc, char *argv[])
{
    char *string;
    if (argc<2)
    {
        printf ("please specify a string parameter.\n");
        exit (0);       
    }

    string = argv[1];
    int i;

    int is_unique = 1;
    char *to_check;
    while (*string)
    {
        to_check = string+1;
        while (*to_check)
        {
            //printf ("s = %c, c = %c\n", *string, *to_check);
            if (*to_check == *string)
            {
                is_unique = 0;
                break;
            }
            to_check++;
        }
        string++;
    }

    if (is_unique)
        printf ("string is unique\n");
    else
        printf ("string is NOT unique\n");
}

Without using additional memory:

#define UNIQUE_ARRAY 1
int isUniqueArray(char* string){
    if(NULL == string ) return ! UNIQUE_ARRAY;
    char* current = string;
    while(*current){
        char* next   = current+1;
        while(*next){
            if(*next == *current){
                return ! UNIQUE_ARRAY;
            }
            next++;
        }
        current++;
    }
    return UNIQUE_ARRAY;
}

I beleive there is a much simpler way:

int check_string_unique(char *str) 
{
   int i = 0;
   int a = 0;
   while (str[i])
   {
      a = i + 1; // peak to the next character
      while (str[a])
      {
          if (str[i] == str[a]) // you found a match
             return (0); // false
          a++; // if you've checked a character before, there's no need to start at the beggining of the string each time. You only have to check with what is left.
      }
   i++; //check each character.
   }
return (1); //true!
}

I hope this can help you

#include <iostream>
using namespace std;
int main() {
 string s;
 cin>>s;
 int a[256]={0};
 int sum=0;
 for (int i = 0; i < s.length();i++){
    if(a[s[i]]==0)++sum;
    a[s[i]]+=1;
 }
 cout<<(sum==s.length()?"yes":"no");
 return 0;

}

this is optimal solution for the problem. it takes only an integer variable and can tell whether it is unique or not regardless of string size.

complexity

best case O(1)

worst case O(n)

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - ‘a’;
        if ((checker & (1 << val)) > 0) 
            return false;
        checker |= (1 << val);
    }
    return true;
}