Необходимо уменьшить количество рекурсивных вызовов в этой функции

Question

Задаче задана строка S и целое число k

Answer 1

он говорит, что у меня слишком много рекурсивных вызовов для других тестовых случаев

Я удивлен, что он потерпел неудачу при рекурсивных вызовах, прежде чем он потерпел неудачу из-за слишком много времени, чтобы придумать ответ . Глубина рекурсии такая же, как k, поэтому k пришлось бы достичь 1000 для Python по умолчанию, чтобы подавиться. Однако вашему коду требуется 4 минуты для решения того, что кажется простым примером:

print(stringReduction(8, "dermosynovitis"))

Количество времени является функцией k и длины строки. Проблема, на мой взгляд, рекурсивно, заключается в следующем коде:

for i in range(len(s)):
    new_str = s[:i]+s[i+1:]
    strings = allPossibleCombinations(k-1, new_str, strings, depth + 1)

После того, как мы удалили первый символ say и выполнили все комбинации без него, ничто не остановит рекурсивный вызов, который отбрасывает второй символ снова удаляет первый символ и пробует все комбинации. Мы (повторно) тестируем слишком много строк!

Основная проблема c в том, что вам нужно обрезать (т.е. избегать) строк при тестировании, а не генерировать все возможностей и протестируйте их. Если первая буква кандидата меньше, чем лучшая строка, которую вы видели до сих пор, никакие манипуляции с оставшимися символами в этом кандидате не улучшат ее.

Answer 2

Это должно помочь вам начать -

from itertools import combinations

def all_possible_combinations(k = 0, s = ""):
  yield from combinations(s, len(s) - k)

Теперь для заданных k=2 и s="abcde" мы показываем все комбинации s с удаленными k символами -

for c in all_possible_combinations(2, "abcde"):
  print("".join(c))

# abc
# abd
# abe
# acd
# ace
# ade
# bcd
# bce
# bde
# cde