C语言 确定一个字符串是否具有所有唯一字符？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4987863/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
determine if a string has all unique characters?
提问by mr_eclair
Can anybody tell me how to implement a program to check a string contains all unique chars ?
谁能告诉我如何实现一个程序来检查字符串是否包含所有唯一字符？
回答by mrcrowl
If you are talking about an ASCII string:
如果您在谈论 ASCII 字符串：
Create an int array [0-255], one for each character index, initialised to zero.
Loop through each character in the string and increment the respective array position for that character
If the array position already contains a 1, then that character has already been encountered. Result => Not unique.
If you reach the end of the string with no occurrence of (3), Result => the string is unique.
创建一个 int 数组 [0-255]，每个字符索引一个，初始化为零。
循环遍历字符串中的每个字符并增加该字符的相应数组位置
如果数组位置已包含 1，则已遇到该字符。结果 => 不是唯一的。
如果到达字符串的末尾而没有出现 (3)，则 Result => 该字符串是唯一的。
回答by Matteo Italia
Sort the characters in the string using your algorithm of choice (e.g. the builtin qsortfunction), then scan the string checking for consecutive repeating letters; if you get to the end without finding any, the string contains all unique characters.
使用您选择的算法（例如内置qsort函数）对字符串中的字符进行排序，然后扫描字符串检查连续重复的字母；如果你到最后没有找到任何字符，则该字符串包含所有唯一字符。
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.
另一种方法可能是使用一些结构，该结构为字符串可能包含的每个字符都有一个桶，所有字符都初始化为零；您扫描字符串，增加与当前字符对应的存储桶的值。如果你要增加一个里面已经有 1 的存储桶，你肯定你的字符串包含重复项。
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.
这可以很好地处理chars 和一个数组（大小为UCHAR_MAX+1），但是当您开始处理宽字符时，它很快就会失控。在这种情况下，您需要一个哈希表或其他一些“严重”的容器。
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.
最佳算法取决于要检查的字符串的长度、每个字符的大小、排序算法的速度以及分配/使用结构来保存字符频率的成本。
回答by user673558
#include <iostream>
#include <string>
using namespace std;
bool isUnique(string _str)
{
bool char_set[256];
int len = _str.length();
memset(char_set, 'def hasUniqueLetters(str):
return (len(set(str)) == len(str))
>>> hasUniqueLetters("adoihgoiaheg")
False
', 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;
}
回答by Phil H
Make a set of the letters, and count the values.
制作一组字母，并计算值。
set("adoihgoiaheg")= set(['a', 'e', 'd', 'g', 'i', 'h', 'o']):
set("adoihgoiaheg")= set(['a', 'e', 'd', 'g', 'i', 'h', 'o'])：
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;
}
回答by lhf
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.
使用 256 个条目的数组。用 0 填充它。现在遍历字符串，如果它是 0，则将数组中的相应条目设置为 1。否则，字符串中有重复的字符。
回答by Ira Baxter
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.
将大小等于字符集的布尔数组设置为 false。（恒定时间）。扫描字符串；对于每个字符，检查字符槽中的数组；如果为 true，则字符串具有重复字符。如果为 false，则将该插槽设置为 true 并继续。如果你在没有遇到重复的情况下走到最后，则没有任何重复，并且字符串仅包含唯一字符。运行时间：O(n)，当 n 是字符串的长度时，常量很小。
回答by Matthew
Similarly (and without arrays), use a HASH TABLE!
同样（并且没有数组），使用哈希表！
//psuedo code:
//伪代码：
- go through each char of the string
- hash the char and look it up in the hash table
- if the table has the hash, return FALSE // since it's not unique
- __else store the hash
- return to step #1 until you're done
- 遍历字符串的每个字符
- 散列字符并在散列表中查找
- 如果表有散列，则返回 FALSE // 因为它不是唯一的
- __else 存储哈希
- 返回第 1 步，直到完成
Run time is O(n) and memory space is better too since you don't need an array of 256 (asciis)
运行时间是 O(n) 并且内存空间也更好，因为您不需要 256 (asciis) 的数组
回答by ANK
Simple solution will be using 2 loops. No additional data structure is needed to keep a track on characters.
简单的解决方案将使用 2 个循环。不需要额外的数据结构来跟踪字符。
#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;
}
回答by asterix
回答by user2744865
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.
使用 HashTable，添加每个字符的键以及出现次数作为值。循环遍历 HashTable 键以查看是否遇到计数 > 1。如果是，则输出 false。
