隣接するペアの重複の削除

Question

のいずれかのペアを同じ値の隣接するの文字を削除する。たとえば、文字列 "aabcc"は操作後に "aab"または "bcc"になります。

サンプル入力は=
サンプル出力をaaabccddd = ABD

重複し、それらを取り除くにマッチするように、リストまたは文字列を反復処理する方法が混乱は、ここで私がしようとしていますし、私はそれを知っている方法です間違っている。

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から問題である：奇数がある場合、それらの偶数、1が存在する場合ペア文字を削除Super Reduced String

Answer 1

は空の配列に文字のランを低減することを低減することができます。 aaaaaaが空になると、aaaaaはaに縮小されます。 Hackerrankが与えるために、しかし

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] 

：

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

はその後、もはや変更シーケンスの大きさになるまで繰り返します。

は、グループサイズを、任意の順序でこれを行う itertools.groupby()を使用してカウントしますあなた のテキスト正規表現でこれを実行した方が速いでしょう：

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（） `はすべてのパターンを空のテキストに置き換えます。

正規表現のアプローチは、そのHackerrankチャレンジに合格するのに十分です。

Answer 2

O（n）時間の複雑さを達成するためにスタックを使用できます。文字列内の文字を繰り返し、各文字のチェックで、スタックの先頭に同じ文字が含まれているかどうかを確認します。場合は、スタックからキャラクターをポップし、次のアイテムに移動します。それ以外の場合は、文字をスタックにプッシュします。私は正規表現の速度を測定し、100の入力長とベースのソリューションを積層するテストのカップルを走った議論に基づいて

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 

更新：スタック内に残っているものは何でも結果です。テストでは、Windows 8上のPython 2.7上で実行されました：ベンチマークに使用

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