определить, содержит ли строка все уникальные символы?

<p>кто-нибудь может сказать мне, как реализовать программу для проверки строки содержит все уникальные символы?</p>

<p>если вы говорите о строке ascii:</p><ol> <li> <p>создайте массив int [0-255], по одному для каждого индекса символа, инициализированный нулем.</p> </li> <li> <p>перебирайте каждый символ в строке и увеличивайте соответствующую позицию массива для этого символа</p> </li> <li> <p>если позиция массива уже содержит 1, то этот символ уже встречался. результат => не уникален.</p> </li> <li> <p>если вы достигли конца строки без вхождения (3), result => строка является уникальной.</p> </li> </ol>

<p>сортируйте символы в строке, используя выбранный вами алгоритм (например, встроенную функцию <code>qsort</code>), затем сканируйте строку, проверяя наличие повторяющихся повторяющихся букв; если вы дошли до конца, не найдя ничего, строка содержит все уникальные символы.</p><p>альтернативой может быть использование некоторой структуры, которая имеет один сегмент для каждого символа, который может содержать строка, причем все инициализируются нулем; вы сканируете строку, увеличивая значение корзины, соответствующее текущему символу. если вы увеличиваете интервал, в котором уже есть 1, вы уверены, что ваша строка содержит дубликаты.</p><p>это может нормально работать с <code>char</code>s и массивом (размером <code>uchar\_max+1</code>), но быстро выходит из-под контроля, когда вы начинаете работать с широкими символами. в таком случае вам понадобится хеш-таблица или какой-то другой "серьезный" контейнер.</p><p>лучший алгоритм зависит от длины проверяемых строк, размера каждого символа, скорости алгоритма сортировки и стоимости выделения/использования структуры для хранения частот символов.</p>

<pre><code>#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; } </code></pre>

<p>составьте набор букв и посчитайте значения.</p><p><code>set("adoihgoiaheg")</code> = <code>set(['a', 'e', 'd', 'g', 'i', 'h', 'o'])</code>:</p><pre><code>def hasuniqueletters(str): return (len(set(str)) == len(str)) >>> hasuniqueletters("adoihgoiaheg") false </code></pre>

<p>используйте массив из 256 записей. заполните его 0. теперь переберите строку, установив для соответствующей записи в массиве значение 1, если оно равно 0. в противном случае в строке повторяются символы.</p>

<p>точно так же (и без массивов) используйте hash table!</p><p>// код псевдо:</p><ol> <li>пройти через каждый символ строки</li> <li>хэшируйте char и ищите его в хеш-таблице</li> <li>если таблица имеет хеш, возвращает false //, поскольку она не уникальна</li> <li>еще хранить хеш</li> <li>возвращайтесь к шагу № 1, пока не закончите</li> </ol><p>время выполнения - o(n), и пространство памяти также лучше, так как вам не нужен массив из 256 (asciis)</p>

<p>установите массив логических значений размера, равного значению false. (постоянное время). сканирование строки; для каждого символа осмотрите массив в слоте персонажа; если true, строка содержит повторяющиеся символы. если false, установите для этого слота значение true и продолжайте. если вы дошли до конца, не встретив дубликата, их там нет, и строка содержит только уникальные символы. время выполнения: o(n), когда n - длина строки с довольно маленькой константой.</p>

<p>простое решение будет использовать 2 цикла. для отслеживания символов не требуется никакой дополнительной структуры данных.</p><pre><code>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; } </code></pre>

<p>используйте hashtable, добавьте ключ для каждого символа вместе с количеством вхождений в качестве значения. выполните циклическое переключение клавиш hashtable, чтобы увидеть, встречались ли вы с числом> 1. если да, выведите false.</p>

<pre><code>#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; } </code></pre>

<p>это оптимальное решение проблемы. она принимает только целочисленную переменную и может сказать, является ли она уникальной или нет, независимо от размера строки.</p><blockquote> <h2>сложность</h2> <p>лучший случай o (1)</p> <p>наихудший случай o (n)</p> </blockquote><pre><code>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; } </code></pre>

<p>я считаю, что есть гораздо более простой способ:</p><pre><code>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! } </code></pre>

<p>я надеюсь это тебе поможет</p><pre><code>#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; </code></pre><p>}</p>

<p><strong>без использования дополнительной памяти:</strong></p><pre><code>#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; } </code></pre>

<pre><code>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; } </code></pre>

<p>мой оригинальный ответ также выполнял аналогичную технику массива и подсчитывал вхождение символов.</p><p>но я делал это в c, и я думаю, что это может быть просто, используя некоторые манипуляции с указателями и полностью избавиться от массива</p><pre><code>#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"); } </code></pre>