Здравствуйте, sergeya, Вы писали:

S>Пусть word можно составить как из subword1, так из subword2 + subword3.
S>Приведенное условие имхо остановит перебор как только встретится subword1.

Нет, не остановит. Это часть цикла, в котором мы пробегаем по всем возможным подсловам. После выполнения этого условия мы перейдем к рассмотрению следующего возможного подслова (на операторе continue)

Можно переписать так (может легче будет воспринимать конечное условие рекурсии):

    @lru_cache
    def split_word(word: str) -> List[List[str]]:
        """Находит все варианты разбиения слова word на подстроки из strings"""

        if word == "":
            return [[]]

        result = []
        for subword in strings:
            if not word.startswith(subword):
                continue
            rest_word = word[len(subword):]
            for rest_combination in split_word(word=rest_word):
                result.append([subword, *rest_combination])
        return result

Здравствуйте, Буравчик, Вы писали:

Б>Нет, не остановит. Это часть цикла, в котором мы пробегаем по всем возможным подсловам. После выполнения этого условия мы перейдем к рассмотрению следующего возможного подслова (на операторе continue)

Ты прав. Там же не выход из процедуры, а только переход к следующему слову.

Здравствуйте, Буравчик, Вы писали:

Б>Сложность тоже интересно посчитать (не получилось сразу, не буду выкладывать)

ну раз ДП то добавь мемоизацию и посчитай сколько ключей там будет храниться

Здравствуйте, scf, Вы писали:

scf>Что-то здесь не так. Даже упрощенная задача "найти самое часто встречающееся число в потоке" требует хранения всех чисел со счетчиками в памяти

ну если прямо вот так в память не влазит, то можно и на диск выгружать.
а может им примерно сойдет, то можно Count–min sketch прикрутить

Здравствуйте, baxton_ulf, Вы писали:

_>ну раз ДП то добавь мемоизацию и посчитай сколько ключей там будет храниться

Мемоизация там есть.

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, baxton_ulf, Вы писали:

_>>ну раз ДП то добавь мемоизацию и посчитай сколько ключей там будет храниться

Б>Мемоизация там есть.

чет lru_cache сразу не заметил