повторно удалять вхождения подстроки, пока основная строка не станет пустой

Итак, у меня есть стек и игла:

stack = 'lllolollololollllolol'

needle = 'lol'

Если я каждый раз удаляю один needle из stack в правильном порядке, stack можно очистить, чтобы в конце он был пуст. Например, каждый раз lol, выделенный жирным шрифтом, удаляется (обратите внимание, что после удаления может быть создан еще один needle):

лллоллололлллллллллллллллллл

ллолололололлол

ллололлолололл

ллололололл

ллоллолол

ллолол

лол

очистить

Чтобы найти маршрут, как указано выше, единственный способ, который я придумал с помощью Python, — это использовать регулярное выражение (finditer), чтобы найти все needles в stack, и использовать рекурсию для изучения всех возможных комбинаций удаления, чтобы найти те, которые могут сделать stack пустой. Но я знаю, что это совсем не эффективно.

Есть ли более эффективный способ найти хотя бы 1 способ удалить needle, чтобы очистить stack с помощью Python?

Я нашел эту тему: Рекурсивное удаление вхождений подстроки Но я не уверен, что это 100% применимо к моему случаю.

Спасибо!

Ниже приведен код, который я придумал (плохая сложность, которую я знаю..):

def answer(chunk, word):
    if chunk.find(word) != -1:
        occ = [m.start() for m in finditer('(?='+word+')', chunk)]
        for o in occ:
            new = chunk[:o] + chunk[o + len(word):]
            answer(new, word)
    else:
        result.append(chunk)
        result.sort()
        return chunk
...
#So all the shortest "leftover stack" after the removal are stored in list 
#"result". These include empty or non-empty outputs depending on how 
#the removal was executed.

python string regex substring algorithm
person ZEE    schedule 06.07.2015    source источник
comment
Поскольку SO не является службой написания кода, если вы хотите задать хороший вопрос, пожалуйста, добавьте свой код.   -  person kasravnd    schedule 06.07.2015
comment
ха-ха, да, я бы, наверное, сказал то же самое, если бы увидел такой вопрос. Я написал свой код. И это было частью моего решения задачи foo.bar (отправлено). Я не публиковал код, потому что не был уверен, что он должен быть. Но я обновлю свой вопрос с существенной частью.   -  person ZEE    schedule 08.07.2015

Ответы (3)


arrow_upward
3
arrow_downward

В качестве более общего способа решения таких задач вы можете использовать алгоритм Backtracking.

Вы можете начать с поиска всех needle и начать с выбора между ними и просто удалить варианты, которые столкнутся с критическим состоянием в следующем состоянии. И продолжить проверку других needle.

person kasravnd    schedule 06.07.2015

arrow_upward
3
arrow_downward

Вы можете рекурсировать:

import re

def find_all(bigstr, smallstr):
    return [m.start() for m in re.finditer(smallstr, bigstr)]

def removeNeedle(stack, needle, prev):
    if len(stack) == 0:
        print prev
    indices = find_all(stack, needle)
    for index in indices:
        newStack = stack[:index] + stack[index+3:]
        newPrev = list(prev)
        newPrev.append(index)
        removeNeedle(newStack, needle, newPrev)

stack = 'lllolollololollllolol'
needle = 'lol'

removeNeedle(stack, needle, [])

Это позволит найти все такие возможные решения. Некоторые из возможных результатов следующие:

[2, 1, 5, 1, 0, 1, 0]
[2, 1, 5, 1, 4, 0, 0]
[2, 1, 5, 1, 4, 3, 0]
[2, 1, 5, 7, 1, 0, 0]
[2, 1, 5, 7, 1, 3, 0]
[2, 1, 5, 7, 6, 1, 0]
[2, 1, 10, 5, 1, 0, 0]
[2, 1, 10, 5, 1, 3, 0]
[2, 1, 10, 5, 6, 1, 0]
[2, 1, 10, 9, 5, 1, 0]
[2, 4, 5, 1, 0, 1, 0]
[2, 4, 5, 1, 4, 0, 0]
[2, 4, 5, 1, 4, 3, 0]
[2, 4, 5, 7, 1, 0, 0]
[2, 4, 5, 7, 1, 3, 0]
[2, 4, 5, 7, 6, 1, 0]

Вы можете визуализировать их, используя:

def visualize(stack, prev):
    for p in prev:
        print stack
        print ' ' * p + '---'
        stack = stack[:p] + stack[p+3:]

visualize(stack, [2, 1, 5, 1, 0, 1, 0]) # one of the results

Дает тебе:

lllolollololollllolol
  ---
llollololollllolol
 ---
llololollllolol
     ---
llololllolol
 ---
lolllolol
---
llolol
 ---
lol
---

PS: Этот метод имеет экспоненциальную сложность по времени и составляет stack.

person Sait    schedule 06.07.2015

arrow_upward
-2
arrow_downward

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

stack = 'lllolollololollllolol'
needle = 'lol'

while needle in stack:
    stack = stack.replace(needle, '')

print stack
person kyle k    schedule 06.07.2015
comment
2 минуса без комментариев?? - person anubhava; 06.07.2015
comment
Это заменит только первое вхождение, оно может дать или не дать вам правильный результат. См. алгоритмы поиска с возвратом. - person Sait; 06.07.2015
comment
Например, это не будет работать с этим примером: stack= 'lololl', needle='lol'. - person Sait; 06.07.2015