python3-文字列で隣り合う同じ文字を削除したい-

Question

文字列から隣り合う同じ文字を削除したい

例えば、"aabcacc"という文字列があった場合
「aa」と「cc」を削除して 「bca」となるようにしたい。

"abbac"であれば、「bb」を削除したら「aac」になり、「aa」を削除して最終的に「c」になる
今回はこの"abbac"を想定してコードを書いています。

s="abbac"

a=[]
b=[]
for i in range(len(s)):
    a.append(s[i])

count = 0
while True:
    for j in range(len(a)-1):
        if a[j] == a[j+1]:
            b.append(a[j])
            b.append(a[j+1])
            count += 1
    if count == 0:
        break
    else:
        count = 0

set_ab = set(a) - set(b)
list_ab = list(set_ab)
print(list_ab)

発生したエラー

• ループから抜け出せない

なぜこのコードでは抜け出せられないのでしょうか・・・？

• 文字列の文字が操作できないらしい？(あまり詳しくないので、ネット情報です)

文字列の文字の操作がreplace(s[0], "")のようにできないようだったので、
遠回りかもしれませんが、一度一文字ずつリストに格納して、delで削除することにしました。

###質問したいこと

• 本当はリストを使うなんて遠回りしない方が良いのですが、リストを使わない場合、文字列の操作ができないという問題をどのように解決するのでしょうか？

• なぜこのコードのbreakでループを終わらせられないのでしょうか？

*なにかアドバイスがあればどんなことでもいいのでお願いします。

Comments

[退会済みユーザー]

３文字連続してる場合はどうします？

[n_oshiumi]

"aaa"とあったら、ペア(aa)を削除するようにしていますので、aが残ります！

Answer 1

正規表現を使うといいと思います。

import re
a="abcddefgghiiiij"
b=re.sub("([a-z])\1", "", a)
print(b)

追記:

"aaa"とあったら、ペア(aa)を削除するようにしていますので、aが残ります！

という質問者の追加コメントに対応してみます。「否定先読み」を使い、「a-zのどれかが存在し、直後に同じ文字が続き、しかしその直後にその文字は続かない」を表現します。

import re
a="abcddefgghiiiij"
b=re.sub("([a-z])\1(?!\1)", "", a)
print(b)

Comments

[n_oshiumi]

正規表現は難しくて、未だに上手くできないのですが、
正規表現でこんなこともできることを知って、もう少し勉強してみようと思いました。
ありがとうございました！

[katoy]

>>> print(re.sub("([a-z])\1(?!\1)", "", "aabcacc"))
bca
>>> print(re.sub("([a-z])\1(?!\1)", "", "abbac"))
aac
となります。
これは質問者が求めている結果と一致してますか？

[KojiDoi]

第2段落を完全に見落としてました。確かに他の回答にあるようなループ処理が必要になりそうですね。

Answer 2

リストを使わない場合

リストのようなコレクション的なものを作ってそれを加工するというのも別に悪くないのですが、「要素を一つ一つ流れ作業で料理する」という考え方が使えるような場合もかなり多いと思います。

functools.reduceを使った例を挙げてみます。reduceは要素を一つずつ取り出しては

... f(f(f(e0, e1), e2), e3) ...

というような関数の適用を繰り返して結果を求めてくれます。

fの第一引数は「前の要素までの簡約結果」で第二引数は「次の要素」です。本件の場合簡約結果を「連続した２つの文字を取り除いた結果」と考えると、以下のように書けます。

import functools

def drop_same(s, c):
  return s[:-1] if s != '' and s[-1] == c else s + c

functools.reduce(drop_same, 'abbac', '')      #  'c'
functools.reduce(drop_same, 'zabbaccz', '')   #  ''

---

Python 3.6.0

Comments

[退会済みユーザー]

興味でご質問したいのですが、対象も文字列に連続して3回文字が並ぶと1個残ってしまうのはどうしてですか？まだきちんとフローを終えてない状態で恐縮なのですが・・・

[退会済みユーザー]

すいません、理解できました。マッチングが取れた時点で末尾と次の入力の両方を落としてるためですね。大変失礼しました。

[n_oshiumi]

いえいえ、質問ありがとうございます！！

[n_oshiumi]

ごめんなさい、自分への質問化と思って、返事をしたつもりでした、間違えました。。。
functools.reduceは知らなかったので、タメになりました！ありがとうございました！

[KSwordOfHaste]

ペア単位で削除するか2個以上の連続を削除するかはあまりきにせず前者にしました。後者にするならまた別の工夫が必要ですね。仮にreduceを使うとしたらs[-1]がcと違うことがわかった時点でs[i:-1]が全部同じ文字になるようなiを求めてi<-1ならその範囲を削除・・・とかでしょうか。ややこしくてreduceの単純さがなくなっちゃいそうです。

Answer 3

whileでループが回るたびに、内側のforが文字列を最初から最後までスキャンしてしまっています。今の入力では、連続する文字列があるので、forを回す間にcountが1になってしまい、決してbreakには到達できなくなっていますよ。

Comments

[n_oshiumi]

あ、なるほど、確かにそうですね。
最初にdelを使用してやってみたのですが、
「list index out of range」というエラーが出ます。

最初にrange(len(a)-1)とやっているのに、
途中でリストの数が減って、計算が合わなくなったことが原因だと思われるのですが、
このときの対処法がもし分かるようでしたら、教えていただきたいです。

Answer 4

itertools.groupbyを使うのはいかがでしょうか。

from itertools import groupby

def has_serial_duplicated_chars(src_str):
    return any(
        ch1 == ch2 for ch1, ch2 in zip(src_str, src_str[1:])
    )

def remove_serial_duplicated_chars(src_str):
    while has_serial_duplicated_chars(src_str):
        src_str = ''.join(
            k for k, gen in groupby(src_str) 
            if sum(1 for _ in gen) % 2 == 1
        )
    
    return src_str 


print(
    remove_serial_duplicated_chars('abbac')
)
print(
    remove_serial_duplicated_chars('abbbac')
)

実行結果 Wandbox

c
abac

過去の修正について

仕様の誤認が度重なり、二度にわたり大々的に回答を変更しています。
本来なら過去の回答に追記する形が良いのでしょうが、可読性を考慮し上書き修正いたしました。

Answer 5

自分で loop を回して処理する版と、正規表現を使う版を書いてみました。
replace.py

import re

def reduce_1(s):
    a = []
    b = []
    for i in range(len(s)):
        a.append(s[i])

    while True:
        j = 0
        while j < len(a):
            if j == len(a) - 1:
                b.append(a[j])
            elif (a[j] == a[j + 1]):
                j += 1
            else:
                b.append(a[j])
            j += 1

        if len(a) == len(b):
            break
        a = b
        b = []

    return b


def reduce_2(s):
    while True:
        ss = re.sub("(.)\1", "", s)
        if s == ss:
            return ss
        s = ss


print(reduce_1("aabcacc"))
print(reduce_1("abbac"))

print(reduce_2("aabcacc"))
print(reduce_2("abbac"))

実行霊：

Answer 6

import re
def super_reduced_string(s):
    for i in range(len(s)):
        s=re.sub("([a-z])\1", "", s)
        if len(s) == 0:
            print("Empty String")
            break
    print(s)