многократно премахване на появявания на подниз, докато основният низ е празен

Така че имам стека и иглата:

stack = 'lllolollololollllolol'

needle = 'lol'

Ако премахвам едно needle от stack всеки път, с правилния ред, stack може да бъде изчистено, така че да е празно в края. Например, всеки път lol с удебелен шрифт се премахва (забележете, че друг needle може да бъде допълнително създаден след премахването):

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

лолололололохаха

лелололололо

лололололл

лоллолол

лхахаол

хаха

изчистване

За да намеря маршрут като по-горе, единственият начин, който измислих с помощта на Python, е да използвам regex (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.

Можете да започнете, като намерите всички needles и да започнете, като изберете между тях и просто премахнете изборите, които ще срещнат критично състояние в тези следващи състояния. и продължете да проверявате други needles.

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