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

任何人都可以告诉我如何实现一个程序来检查包含所有唯一字符的字符串?

如果你在谈论ASCII字符串:

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

  2. 循环遍历字符串中的每个字符,并递增该字符的相应数组位置

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

  4. 如果到达字符串的末尾而没有出现(3),则Result =>字符串是唯一的。

使用您选择的算法(例如内置qsort函数)对字符串中的字符进行排序,然后扫描字符串检查连续的重复字母; 如果你没有找到任何结果,那么该字符串包含所有唯一字符。

替代方案可能是使用一些结构,该结构对于字符串可能包含的每个字符都有一个桶,所有这些都初始化为零; 扫描字符串,增加与当前字符对应的存储桶的值。 如果您要增加一个已经有1的存储桶,您确定您的字符串包含重复项。

这可以很好地使用char和一个数组(大小为UCHAR_MAX+1 ),但是当你开始处理宽字符时很快就会失控。 在这种情况下,您需要哈希表或其他“严重”容器。

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

 #include  #include  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: "< 

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

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

 def hasUniqueLetters(str): return (len(set(str)) == len(str)) >>> hasUniqueLetters("adoihgoiaheg") False 

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

设置一个大小等于字符集为布尔值的布尔数组。 (恒定时间)。 扫描字符串; 对于每个角色,在角色的位置检查arrays; 如果为true,则string具有重复的字符。 如果为false,则将该槽设置为true并继续。 如果你在没有遇到重复的情况下到达最后,则没有任何内容,字符串只包含唯一字符。 运行时间:O(n)当n是字符串的长度时,具有非常小的常量。

类似地(没有数组),使用HASH TABLE!

// psuedo代码:

  1. 遍历字符串的每个字符
  2. 对char进行哈希并在哈希表中查找
  3. 如果表有哈希值,则返回FALSE //因为它不是唯一的
  4. __else存储哈希值
  5. 回到第1步,直到你完成

运行时间为O(n),内存空间也更好,因为您不需要256(asciis)数组

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

使用HashTable,为每个字符添加键以及出现次数作为值。 循环访问HashTable键以查看是否遇到计数> 1.如果是,则输出false。

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

 bool has_unique_char(char *str,int n) { if(n==0) return true; for(int i=1;i 
 bool isUnique(char st[],int size) { bool char_set[256]=false; for(int i=0;i 

我的原始答案也是做类似的数组技术并计算字符的出现次数。

但我在C中做它,我认为使用一些指针操作可以很简单,完全摆脱arrays

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

不使用额外的内存:

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

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

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

我希望这可以帮到你

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

}

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

复杂

最佳案例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; }