Поиск всех комбинаций слов, образующих слово

Можете ли вы использовать каждое слово только один раз? Например, если у вас есть de и dede, является ли (de, de) ответом? Я просто предполагаю, что каждое слово появляется один раз для простоты, у вас много слов, но нет ограничений памяти.

1- построить собственное дерево так, чтобы каждый узел был таким, как показано ниже:

class node():
   is_there_a_word_that_ends_here = T/F
   children = dict() # other nodes, key is the letter of the node

, например, если у вас есть три слова, такие как ["ab", "abc", "ade "," c "] тогда у вас будет дерево, как показано ниже (я поставлю знак *, если значение узла is_there_a_word_that_ends_here равно true)

head ---a---b*---c*
    |   |
    |   L-d----e*
    |
    L--c*

2-групповые слова по длине. начните со слова с наименьшей длиной, потому что вы хотели бы знать «разбивки» более мелких слов, когда вы достигаете более крупных слов. здесь вы можете сделать это рекурсивно с помощью функции скажем add_word_to_result, которая может (должна) кэшировать результаты.

results = dict() # keys: possible words you can reach, values: ways to reach them
for word in words_in_ascending_length:
   add_word_to_result(word, tree, results)

и add_word_to_result начнут двигаться через дерево. если он видит is_there_a_word_that_ends_here в узле, он вызывает add_word_to_result(remaining_part_of_the_word, tree, results). например, если у вас есть «abc», вы увидите * в «ab», а затем позвоните add_word_to_result("c", tree, results).

Реализация рекурсивной функции - это «забавная часть» вопроса (также более трудоемкая), поэтому я оставлю это вам. Кроме того, в качестве бонуса вы можете подумать о том, как избежать добавления дубликатов к результатам эффективным способом (поскольку дубликаты могут возникать в некоторых случаях).

(Изменить: и, возможно, вам нужно кэшировать разбивки для существующих слов и несуществующих слов - разбивку окончания слова, например - отдельно, чтобы вам не приходилось разделять их перед тем, как вернуть результат, если это предложение имеет какой-то смысл)

Надеюсь, это поможет.

Бонус: пример кода (на самом деле его не тестировали, но он должен работать, и есть существенное улучшение, которое вы можете сделать, но мне сейчас лень это делать. Вы можете немного изменить структуру, чтобы передать results - add_word_to_result , так что вы помните все возможные комбинации до настоящего времени, поэтому вместо add_word_to_result(head, head, words_left[1:], combinations, words_passed+words_left[0]+",") вы просто используете это и не делаете ненужной рекурсии)

words = ["leetcode", "leet", "code", "le", "et", "etcode", "de", "decode", "deet"]


class node():
    def __init__(self, letter, is_there_a_word_that_ends_here):
        self.letter = letter # not really used but it feels weird to not have it in class
        self.is_there_a_word_that_ends_here = is_there_a_word_that_ends_here
        self.children = dict()


# actually defining tree is redundant you can just merge tree and node class together, but maybe this is more explicit
class Tree():
    def __init__(self):
        self.head = node(None, False)

    def add(self, word, head=None):
        if head is None:
            head=self.head

        if word[0] not in head.children.keys():
            head.children[word[0]] = node(word[0], False)

        if len(word) == 1:
            head.children[word[0]].is_there_a_word_that_ends_here = True
        else:
            self.add(word[1:], head=head.children[word[0]])


words = sorted(words, key=lambda w: len(w))
results = dict()
tree = Tree()
for word in words:
    tree.add(word)


def add_word_to_result(head, current_node, words_left, combinations, words_passed):
    if words_left[0] in current_node.children.keys():
        # this does not have to happen because we call this function with words that are not in the list as well
        next_node = current_node.children[words_left[0]]
        if len(words_left) == 1 and next_node.is_there_a_word_that_ends_here:
            combinations.append(words_passed+words_left)
        elif next_node.is_there_a_word_that_ends_here:
            add_word_to_result(head, head, words_left[1:], combinations, words_passed+words_left[0]+",")
            add_word_to_result(head, next_node, words_left[1:], combinations, words_passed + words_left[0])
        else:
            add_word_to_result(head, next_node, words_left[1:], combinations, words_passed+words_left[0])


for word in words:
    results[word] = []
    add_word_to_result(tree.head, tree.head, word, results[word], "")

print(results)

# {'le': ['le'], 'et': ['et'], 'de': ['de'], 'leet': ['le,et', 'leet'], 'code': ['code'], 'deet': ['de,et', 'deet'], 'etcode': ['et,code', 'etcode'], 'decode': ['de,code', 'decode'], 'leetcode': ['le,et,code', 'le,etcode', 'leet,code', 'leetcode']}