函数创建单词树

Question

我想创建一个接受字符串的函数。从提供的字符串中，我想从字符串中提取一个字母，并将其添加到从第一个位置到最后一个位置的每个位置的字符串中。你知道吗

我想一直这样做，直到我有一个完全有意义的词（我有一个“有意义”的词字典，我会检查）

这是我想要的一个例子（从'posta'[对不起意大利人]，然后改成posta sposta sposta sposta spossata…）。。。以此类推）：

posta
    sposta
        esposta
        sposata
            spossata
            spostata
        spostai
            spostati
                spostarti
                spostasti
            spostavi
                spostarvi
    posata
        sposata
            spossata
            spostata
    posita

Answer 1

可能是这样的：

#! /usr/bin/python3

import string

#This is your list of valid words
words = ['niente', 'sposta', 'esposta', 'sposata', 'spossata', 'spostata',
'spostai', 'spostati', 'spostarti', 'spostasti', 'spostavi', 'spostarvi',
'posata', 'sposata', 'spossata', 'spostata', 'posita']

class Tree:
    def __init__ (self, payload):
        self.payload = payload
        self.children = []

    def __iadd__ (self, child):
        if child not in self.children:
            self.children.append (child)
        return self

    def pprint (self, indent = 0):
        print (' ' * indent + self.payload)
        for child in self.children:
            child.pprint (indent + 2)

    def __eq__ (self, other):
        return self.payload == other.payload

def expand (word):
    node = Tree (word)
    for c in string.ascii_lowercase: #or whatever caracters you need, maybe also è, ì, etc
        for p in range (len (word) + 1):
            candidate = word [:p] + c + word [p:]
            if candidate in words:
                node += expand (candidate)
    return node

a = expand ('posta')
a.pprint ()

例如，如果将我的'/usr/share/dict/words'作为有效单词，并展开“arm”，则得到：

arm
  farm
    farms
  harm
    charm
      charms
    harem
      harems
    harms
      charms
      harems
  arms
    farms
    harms
      charms
      harems
    warms
      swarms
  warm
    swarm
      swarms
    warms
      swarms
  army