重复删除子字符串直到主字符串为空

Question

所以我有一个堆栈和针头：

堆栈 = 'lllolollololollllolol'

针头 = 'lol'

如果每次从堆栈中删除一个针头，并按正确的顺序进行，堆栈最终可以被清空，使其为空。例如，每次都会删除粗体中的'lol'（注意，在删除后可能会创建另一个针头）： lllolollololollllolol lllolollolololllol lllolollolololl llollolololl llollolol llolol lol 清空

为了找到像上面那样的路径，我唯一想到的使用Python的方法是使用正则表达式（finditer）在堆栈中查找所有的针头，并使用递归来探索所有可能的删除组合，以找到可以使堆栈为空的组合。但我知道这样做效率不高。

是否有更有效的方法使用Python找到至少一种方法将针头移除以清空堆栈？

我发现了这个主题： Remove occurences of substring recursively 但我不确定它是否完全适用于我的情况。

谢谢！

以下是我想出的代码（复杂度很差，我知道...）：

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.

- ZEE

---

由于SO不是一个代码编写服务，如果您想让问题更好，请添加您的代码。 - Mazdak

哈哈，是的，如果我看到这样的问题，我也会这么说。我确实编写了我的代码。它是我foo.bar挑战解决方案的一部分（已提交）。我没有发布代码，因为我不确定是否应该这样做。但我会用必要的部分更新我的问题。 - ZEE

Answer 1

作为解决此类任务的更通用的方法，您可以使用回溯算法。

您可以开始查找所有的needle，然后选择它们之间的选择，并仅删除在下一个状态中遇到关键状态的选择，并继续检查其他needle。

- Mazdak

Answer 2

你可以进行递归：

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

注意：这种方法在stack长度上的时间复杂度是指数级的。

- Sait

Answer 3

你可以使用循环来删除子字符串。

stack = 'lllolollololollllolol'
needle = 'lol'

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

print stack

- kyle k

---

两个莫名其妙的踩？？ - anubhava

这将仅替换第一次出现，可能会或可能不会给您正确的结果。请参见回溯算法。 - Sait

例如，它将无法与这个例子一起工作：stack='lololl'，needle='lol'。 - Sait