Repeatedly removes occurrences of a substring until the main string is empty
So, I have a stack and a needle:
stack = 'lllolollololollllolol'
needle = 'lol'
If I delete one needle
of stack
each time, with the correct order, stack
it can be cleared to be omitted at the end. For example, each time it is deleted lol
in bold (note that after deleting another one can be created needle
):
lllolollolololll lol ol
lllolollolololl lol
lllolol lol ololl
llollolo lol L
llol lol ol
l lol ol
lol
clear
To find a route as shown above, the only way I came up with using Python is to use regex (finditer) to find everything needles
in stack
, and use recursion to explore all possible deletion combinations to find the ones that might make it stack
empty. But I know this is ineffective.
Is there a more efficient way to find at least one way to remove needle
for empty stack
using Python?
I found this thread: Remove recursive substring examples But I'm not sure if this is 100% relevant to my case.
Thank!
Below is the code I ran into (bad complexity I know ..):
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.
source to share
For a more general way of solving such problems, you can use the Backtracking algorithm .
You can start by looking for all needle
and start by choosing between them and just delete the options that will be critical in the next state. and keep checking other needle
s.
source to share
You can recursively:
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, [])
This will find all such possible solutions. Some of the possible outcomes are as follows:
[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]
You can render them using:
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
Gives you:
lllolollololollllolol
---
llollololollllolol
---
llololollllolol
---
llololllolol
---
lolllolol
---
llolol
---
lol
---
PS: This method has exponential time complexity in length stack
.
source to share