déterminer si une chaîne a tous les caractères uniques?

Trier les caractères de la chaîne à l'aide de votre algorithme de choix (par exemple, le groupe builtin qsort fonction), puis analyser la chaîne de la vérification de la continuité de répéter les lettres; si vous arrivez à la fin sans trouver de, la chaîne contient tous les caractères uniques.

Une alternative pourrait être l'utilisation d'une structure qui a un compartiment pour chaque caractère de la chaîne peut contenir, tous initialisés à zéro; vous analysez la chaîne, l'incrémentation de la valeur du seau correspondant à la nature actuelle. Si vous arrivez à incrémenter un seau qui a déjà de 1 à l'intérieur vous êtes sûr que votre chaîne contient des doublons.

Cela peut fonctionner très bien avec chars et un tableau (de taille UCHAR_MAX+1), mais il obtient rapidement de la main lorsque vous commencer à traiter avec les caractères larges. Dans de tels cas, vous avez besoin d'une table de hachage ou d'une autre "sérieux" conteneur.

Le meilleur algorithme dépend de la longueur des chaînes d'examiner, la taille de chaque caractère, la vitesse de l'algorithme de tri et le coût de l'allocation de/à l'aide de la structure pour conserver le caractère fréquences.

Faire une série de lettres, et de compter les valeurs.

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

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

>>> hasUniqueLetters("adoihgoiaheg")
False

Définir un tableau de booléens de taille égale à la jeu de caractères à faux. (Temps Constant). Analyse de la chaîne; pour chaque personnage, inspecter le tableau à la characater du logement; si la valeur est true, la chaîne a des personnages en double. Si la valeur est false, jeu de fente de vrai et de continuer. Si vous arrivez à la fin sans se heurter à un double, il n'y a pas tout et la chaîne ne contient que des caractères uniques. Temps de marche: O(n) où n est la longueur de la chaine, avec une jolie petite constante.

#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;
}

La solution la plus Simple sera à l'aide de 2 boucles.
Aucune autre structure de données est nécessaire pour garder une trace sur les personnages.

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;
}

ma réponse originale à cette question a été également faire le tableau similaire technique et de compter le caractère de l'événement.

mais je le faisais en C et je pense qu'il peut être simple à l'aide de certains de manipulation du pointeur et de se débarrasser de la matrice totalement

#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");
}

Je crois il y a un moyen beaucoup plus simple:

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!
}

c'est la solution optimale pour le problème.
il ne prend qu'une variable de type entier et peut dire si elle est unique ou pas, indépendamment de la taille de la chaîne.

complexité

meilleur des cas O(1)

pire des cas 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;
}