Удаление дубликатов при спаривании рядом

Question

Удаление любой пары смежных писем с одинаковым значением. Например, строка «aabcc» после операции станет либо «aab», либо «bcc».

вход Образец = aaabccddd
Пример вывода = абд

Confused, как просматривать список или строку таким образом, чтобы соответствовать дубликатов и извлекая их, вот так, как я пытаюсь и я это знаю неправильно.

S = input() 
removals = [] 

for i in range(0, len(S)): 
    if i + 1 >= len(S): 
     break 

    elif S[i] == S[i + 1]: 
     removals.append(i)  
     # removals is to store all the indexes that are to be deleted. 
     removals.append(i + 1) 
     i += 1 
    print(i) 
Array = list(S) 
set(removals) #removes duplicates from removals 

for j in range(0, len(removals)): 
    Array.pop(removals[j]) # Creates IndexOutOfRange error 

Это проблема с Hackerrank: Super Reduced String

Answer 1

Удаление парных букв может быть сведены к сокращению тиражей букв в пустую последовательность, если четные их число, 1, если есть нечетное число , aaaaaa становится пустым, aaaaa сокращен до a.

Чтобы сделать это на любой последовательности, используйте itertools.groupby() и подсчитывают размер группы:

# only include a value if their consecutive count is odd 
[v for v, group in groupby(sequence) if sum(1 for _ in group) % 2] 

затем повторять до тех пор, размер последовательности больше не изменяется:

prev = len(sequence) + 1 
while len(sequence) < prev: 
    prev = len(sequence) 
    sequence = [v for v, group in groupby(sequence) if sum(1 for _ in group) % 2] 

Однако, поскольку Hackerrank дает вы текст было бы быстрее, если бы вы сделали это с регулярным выражением:

import re 

even = re.compile(r'(?:([a-z])\1)+') 

prev = len(text) + 1 
while len(text) < prev: 
    prev = len(text) 
    text = even.sub(r'', text) 

[a-z] в регулярном выражении соответствует строчной букве, (..) groups that match, and \ 1 references the first match and will only match if that letter was repeated. (?: ...) + asks for repeats of the same two characters. re.sub() `заменяет все эти шаблоны пустым текстом.

Подход регулярного выражения достаточно хорош, чтобы передать этот вызов Хакерранку.

Answer 2

Вы можете использовать стек для достижения O (n) временная сложность. Итерации над символами в строке и для каждого символа проверяют, содержит ли верхняя часть стека один и тот же символ. В случае, если он выдает символ из стека и переходит к следующему элементу. В противном случае нажмите символ в стек. Все, что остается в стеке результат:

s = 'aaabccddd' 
stack = [] 

for c in s: 
    if stack and stack[-1] == c: 
     stack.pop() 
    else: 
     stack.append(c) 

print ''.join(stack) if stack else 'Empty String' # abd 

Update На основе обсуждения я побежал пару тестов, чтобы измерить скорость регулярных выражений и стека решений, основанных с входной длиной 100. Тесты проводились на Python 2.7 на Windows 8:

All same 
Regex: 0.0563033799756 
Stack: 0.267807865445 
Nothing to remove 
Regex: 0.075074750044 
Stack: 0.183467329017 
Worst case 
Regex: 1.9983200193 
Stack: 0.196362265609 
Alphabet 
Regex: 0.0759905517997 
Stack: 0.182778728207 

код, используемый для сравнительного анализа:

import re 
import timeit 

def reduce_regexp(text): 
    even = re.compile(r'(?:([a-z])\1)+') 

    prev = len(text) + 1 
    while len(text) < prev: 
     prev = len(text) 
     text = even.sub(r'', text) 

    return text 

def reduce_stack(s): 
    stack = [] 

    for c in s: 
     if stack and stack[-1] == c: 
      stack.pop() 
     else: 
      stack.append(c) 

    return ''.join(stack) 


CASES = [ 
    ['All same', 'a' * 100], 
    ['Nothing to remove', 'ab' * 50], 
    ['Worst case', 'ab' * 25 + 'ba' * 25], 
    ['Alphabet', ''.join([chr(ord('a') + i) for i in range(25)] * 4)] 
] 

for name, case in CASES: 
    print(name) 
    res = timeit.timeit('reduce_regexp(case)', 
         setup='from __main__ import reduce_regexp, case; import re', 
         number=10000) 
    print('Regex: {}'.format(res)) 
    res = timeit.timeit('reduce_stack(case)', 
         setup='from __main__ import reduce_stack, case', 
         number=10000) 
    print('Stack: {}'.format(res))