确定字符串是否包含所有唯一字符？

Question

谁能告诉我如何实现一个程序来检查字符串包含所有唯一字符？

Answer 1

如果您正在谈论 ASCII 字符串：

1. 创建一个 int 数组 [0-255]，其中一个
   对于每个字符索引，
   初始化为零。

2. 循环遍历
   字符串中的每个字符和
   增加该字符各自的数组位置

3. 如果数组位置已包含 1，则已遇到该字符。结果=>不唯一。

4. 如果你到达终点
   没有出现的字符串
   (3)、结果=>该字符串是唯一的。

Answer 2

使用您选择的算法（例如内置的 qsort 函数）对字符串中的字符进行排序，然后扫描字符串检查连续的重复字母；如果到达末尾没有找到任何字符，则该字符串包含所有唯一字符。

另一种方法可能是使用某种结构，该结构对于字符串可能包含的每个字符都有一个存储桶，全部初始化为零；您扫描字符串，增加与当前字符对应的存储桶的值。如果您要增加一个内部已经有 1 的存储桶，则可以确定您的字符串包含重复项。

这对于 char 和数组（大小为 UCHAR_MAX+1）可以很好地工作，但是当您开始处理宽字符时，它很快就会失控。在这种情况下，您将需要一个哈希表或其他一些“严肃”的容器。

最好的算法取决于要检查的字符串的长度、每个字符的大小、排序算法的速度以及分配/使用结构来保存字符频率的成本。

Answer 3

制作一组字母，并计算值。

set("adoihgoiaheg") = set(['a', 'e', 'd', 'g', 'i', 'h', 'o'])< /代码>：

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

>>> hasUniqueLetters("adoihgoiaheg")
False

Answer 4

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

Answer 5

使用 256 项数组。用0填充。现在遍历字符串，如果为0则将数组中相应的条目设置为1。否则，字符串中有重复的字符。

Answer 6

将大小等于字符集的布尔数组设置为 false。 （恒定时间）。扫描字符串；对于每个字符，检查该字符槽处的数组；如果为 true，则字符串有重复字符。如果为 false，则将该插槽设置为 true 并继续。如果到达末尾时没有遇到重复字符，则说明不存在重复字符，并且该字符串仅包含唯一字符。运行时间：O(n)，当 n 是字符串的长度时，并且常数非常小。

Answer 7

类似地（并且没有数组），使用哈希表！

//伪代码：

1. 遍历字符串中的每个字符
2. ，对字符进行哈希处理，然后在哈希表中查找，
3. 如果表中有哈希值，则返回 FALSE // 因为它不是唯一的
4. __else 存储哈希值，
5. 返回到步骤#1，直到您'重新完成

运行时间是 O(n) 并且内存空间也更好，因为你不需要 256 (asciis) 的数组

Answer 8

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

Answer 9

使用哈希表，添加每个字符的键以及出现次数作为值。循环遍历 HashTable 键以查看是否遇到 count > > 1. 如果是，则输出 false。

Answer 10

简单的解决方案是使用 2 个循环。
不需要额外的数据结构来跟踪字符。

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

Answer 11

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

Answer 12

我最初的答案也是采用类似的数组技术并计算字符出现的次数。

但我是用 C 语言做的，我认为使用一些指针操作可以很简单并完全摆脱数组

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

Answer 13

不使用额外内存：

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

Answer 14

我相信有一个更简单的方法：

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

Answer 15

我希望这可以帮助你

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

}

Answer 16

这是该问题的最佳解决方案。
它只需要一个整数变量，并且无论字符串大小如何都可以判断它是否唯一。

复杂性

最佳情况 O(1)

最坏情况 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;
}