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

Question

Кто-нибудь может сказать мне, как реализовать программу для проверки строки, содержащей все уникальные символы?

Answer 1

Если вы говорите о строке ASCII:

1. Создайте массив int [0-255], один для каждого индекса символа, инициализируется до нуля.

2. Проход каждый символ в строке и увеличить соответствующую позицию массива для этого символа

3. Если позиция массива уже содержит 1, то этот символ уже встречался. Результат => Не уникален.

4. Если вы дойдете до конца строки без вхождения (3), Результат => строка уникальна.

Answer 2

Сортировка символов в строке с использованием выбранного вами алгоритма (например, встроенной функции qsort), затем проверка строки на наличие последовательных повторяющихся букв;если вы дошли до конца, не найдя ни одного, строка содержит все уникальные символы.

Альтернативой может быть использование некоторой структуры, имеющей один сегмент для каждого символа, который может содержать строка, причем все инициализируются нулем;Вы сканируете строку, увеличивая значение корзины, соответствующее текущему символу.Если вы увеличиваете интервал, в котором уже есть 1, вы уверены, что ваша строка содержит дубликаты.

Это может нормально работать с char s и массивом (размером UCHAR_MAX+1), ноэто быстро выходит из-под контроля, когда вы начинаете иметь дело с широкими символами.В таком случае вам понадобится хеш-таблица или какой-то другой «серьезный» контейнер.

Лучший алгоритм зависит от длины проверяемых строк, размера каждого символа, скорости алгоритма сортировки и стоимости.распределения / использования структуры для хранения частот символов.

Answer 3

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

Составьте набор букв и посчитайте значения.

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

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

>>> hasUniqueLetters("adoihgoiaheg")
False

Answer 5

Использовать массив из 256 записей. Заполните его 0. Теперь переберите строку, установив для соответствующей записи в массиве значение 1, если оно равно 0. В противном случае в строке повторяются символы.

Answer 6

Аналогично (и без массивов) используйте HASH TABLE!

// код псевдо:

1. пройти через каждый символ строки
2. хешируйте char и посмотрите его в хеш-таблице
3. если таблица имеет хеш, вернуть FALSE //, поскольку она не уникальна
4. __ еще хранить хэш
5. возвращайтесь к шагу # 1, пока не закончите

Время выполнения равно O (n), и пространство памяти также лучше, поскольку вам не нужен массив 256 (asciis)

Answer 7

Установить массив логических значений размера, равного значению false.(Постоянное время).Сканирование строки;для каждого символа осмотрите массив в слоте персонажа;если true, строка содержит повторяющиеся символы.Если false, установите для этого слота значение true и продолжайте.Если вы дошли до конца, не встретив дубликата, их там нет, и строка содержит только уникальные символы.Время выполнения: O (n), когда n - длина строки с довольно маленькой константой.

Answer 8

Простое решение будет использовать 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 9

Используйте HashTable, добавьте ключ для каждого символа вместе с количеством вхождений в качестве значения. Выполните циклическое переключение клавиш HashTable, чтобы увидеть, встречались ли вы с числом> 1. Если это так, выведите false.

Answer 10

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