Entfernen von Duplikaten, wenn sie nebeneinander gepaart werden

Question

Löschen eines Paars neben Buchstaben mit demselben Wert. Zum Beispiel würde die Zeichenfolge "aabcc" entweder "aab" oder "bcc" nach der Operation werden.

Probeneingang = aaabccddd
Beispielausgabe = abd

Verwirrt, wie die Liste oder die Zeichenfolge in einer Art und Weise zu durchlaufen die Duplikate zu entsprechen und sie zu entfernen, hier ist die Art und Weise ich versuche und ich weiß es ist falsch.

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 

Dies ist ein Problem von Hackerrank: Super Reduced String

Answer 1

gepaart Buchstaben Entfernen kann auf eine leere Sequenz zur Verringerung der Durchläufe von Buchstaben reduziert werden, wenn es eine gerade Anzahl von ihnen, 1, wenn eine ungerade Zahl sind . aaaaaa wird leer, aaaaa wird auf a reduziert.

diese auf einer beliebigen Reihenfolge zu tun, verwenden itertools.groupby() und die Gruppengröße zählen:

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

dann, bis die Größe der Sequenz wiederholen sich nicht mehr ändert:

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] 

Da jedoch Hackerrank gibt Sie Text wäre es schneller, wenn Sie dies mit einem regulären Ausdruck getan hätten:

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] in einer Regex entspricht einem Kleinbuchstaben, (..) 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() `ersetzt alle diese Muster mit leerem Text.

Der Regex-Ansatz ist gut genug, um diese Hackerrank-Herausforderung zu bestehen.

Answer 2

Sie können den Stack verwenden, um O (n) Zeitkomplexität zu erreichen. Iteriere die Zeichen in einer Zeichenfolge und überprüfe für jedes Zeichen, ob die oberste Ebene des Stapels das gleiche Zeichen enthält. Falls es den Charakter vom Stapel stößt und zum nächsten Gegenstand geht. Ansonsten schiebe das Zeichen auf den Stapel. Was auch immer im Stapel bleibt, ist das Ergebnis:

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 

aktualisiert Auf der Grundlage der Diskussion, die ich lief paar Tests, um die Geschwindigkeit von Regex zu messen und stapeln basierten Lösungen mit Eingabelänge von 100. Die Tests wurden auf Python 2.7 auf Windows 8 laufen:

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 

-Code für Benchmarking:

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))