Удаление дубликатов в строке в Python

Question

Каков эффективный алгоритм удаления всех дубликатов в строке?

Например: aaaabbbccdbdbcd

Требуемый результат: abcd

Answer 1

C ++ - O (n) время, O (1) пробел и выходные данные отсортированы.

std::string characters = "aaaabbbccddd";
std::vector<bool> seen(std::numeric_limits<char>::max()-std::numeric_limits<char>::min());

for(std::string::iterator it = characters.begin(), endIt = characters.end(); it != endIt; ++it) {
  seen[(*it)-std::numeric_limits<char>::min()] = true;
}

characters = "";
for(char ch = std::numeric_limits<char>::min(); ch != std::numeric_limits<char>::max(); ++ch) {
  if( seen[ch-std::numeric_limits<char>::min()] ) {
    characters += ch;
  }
}

Answer 2

Это звучит как идеальное использование для автоматов.

Answer 3

Вы можете отсортировать строку и затем удалить повторяющиеся символы.

#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    std::string s = "aaaabbbccdbdbcd";

    std::sort(s.begin(), s.end());
    s.erase(std::unique(s.begin(), s.end()), s.end());

    std::cout << s << std::endl;
}

Answer 4

В C ++ вы, вероятно, используете std::set:

std::string input("aaaabbbccddd");
std::set<char> unique_chars(input.begin(), input.end());

Теоретически вы можете использовать std::unordered_set вместо std::set, что должно дать O (N) ожидаемую общую сложность (хотя O (N ² ) в худшем случае), где это O ( N lg M) (где N = количество символов, M = количество уникальных символов). Если у вас нет длинных строк с лотом уникальных символов, эта версия, вероятно, будет быстрее.

Answer 5

  string newString = new string("aaaaabbbbccccdddddd".ToCharArray().Distinct().ToArray());   

или

 char[] characters = "aaaabbbccddd".ToCharArray();
                string result = string.Empty ;
                foreach (char c in characters)
                {
                    if (result.IndexOf(c) < 0)
                        result += c.ToString();
                }

Answer 6

O (n) решение:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void removeDuplicates(char *);

void removeDuplicates(char *inp)
{
        int i=0, j=0, FLAG=0, repeat=0;

     while(inp[i]!='\0')
    {
        if(FLAG==1)
        {
                inp[i-repeat]=inp[i];
        }
        if(j==(j | 1<<(inp[i]-'\0')))
        {
                repeat++;
                FLAG=1;
        }
                j= j | 1<<(inp[i]-'\0');
                i++;
    }

     inp[i-repeat]='\0';
}

int main()
{
     char inp[100] = "aaAABCCDdefgccc";
    //char inp[100] = "ccccc";
    //char inp[100] = "\0";
    //char *inp = (char *)malloc(sizeof(char)*100);

    printf (" INPUT STRING : %s\n", inp);

     removeDuplicates(inp);

    printf (" OUTPUT STRING : %s:\n", inp);
    return 1;
}

Answer 7

Возможно, использование встроенных функций Python более эффективно, чем те, которые "сделаны сами".Например:

=====================

ПРИМЕЧАНИЕ: поддерживать порядок

CODE

string = "aaabbbccc"

product = reduce((lambda x,y: x if (y in x) else x+y), string)

print product

ВЫХОД

abc

===============================

ПРИМЕЧАНИЕ: заказ игнорируется

КОД

string = "aaabssabcdsdwa"

str_uniq = ''.join(set(string))

print str_uniq

ВЫХОД

acbdsw

Answer 8

в C, вот как я это сделал: O (n) во времени, поскольку у нас есть только один цикл for.

void remDup(char *str)
{
    int flags[256] = { 0 };

    for(int i=0; i<(int)strlen(str); i++) {
        if( flags[str[i]] == 0 )
            printf("%c", str[i]);

        flags[str[i]] = 1;
    }
}