it-swarm-ru.tech

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

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

12
mr_eclair

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

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

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

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

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

38
mrcrowl

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

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

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

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

7
Matteo Italia
#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;
    }
6
user673558

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

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

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

>>> hasUniqueLetters("adoihgoiaheg")
False
4
Phil H

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

3
lhf

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

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

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

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

2
Matthew Chan

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

2
Ira Baxter

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

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

1
user2744865
#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;
}
1
asterix

это оптимальное решение проблемы. она принимает только целочисленную переменную и может сказать, является ли она уникальной или нет, независимо от размера строки.

сложность

лучший случай 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;
}
0
BlackHawk

Я считаю, что есть гораздо более простой способ:

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

Я надеюсь это тебе поможет

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

}

0
ayush saluja

без использования дополнительной памяти:

#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;
}
0
Madhu S. Kapoor
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;
}
0
Sumit Gaur

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

но я делал это в 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");
}
0
ledmirage