This class implements a trie (prefix tree) data structure in Python // Этот класс реализует структуру данных Префиксное древо на Python

trie.py

class Trie:
    class Node:
        def __init__(self, char=None):
            self.children = []
            self.char = char
            self.is_leaf = False
 
        def put(self, child_node):
            self.children.append(child_node)
 
        def is_contain(self, char):
            for child in self.children:
                if child.char == char:
                    return True
            return False
 
        def get_child(self, char):
            for child in self.children:
                if child.char == char:
                    return child
 
        def get_child_words(self):
            result = []
            for child_node in self.children:
                if child_node.is_leaf:
                    result.append(child_node.char)
                for word in child_node.get_child_words():
                    result.append(child_node.char + word)
            return result
 
    def __init__(self):
        self.root = self.Node()
 
    def add(self, word):
        """
        add word
        """
        current_node = self.root
        for char in word:
            if not current_node.is_contain(char):
                new_node = self.Node(char)
                current_node.put(new_node)
            current_node = current_node.get_child(char)
        if current_node != self.root:
            current_node.is_leaf = True
        return 'Done'
 
    def add_multi(self, string):
        """
        add multiple words separated by ","
        """
        for word in string.split(','):
            self.add(word.strip())
 
    def contains(self, string):
        """
        return true or false
        """
        current_node = self.root
        for char in string:
            if current_node.is_contain(char):
                current_node = current_node.get_child(char)
            else:
                return False
        return True
 
    def find(self, search_string):
        """
        return list of words or empty list
        """
        if len(search_string) < 1:
            return 'too short string'
        current_node = self.root
        for char in search_string:
            if current_node.is_contain(char):
                current_node = current_node.get_child(char)
            else:
                return []
        return map(lambda word: search_string + word, current_node.get_child_words())
 
 
 
words = """
        xp, xx, xii, xiv, xix, xvi, xxi, xxv, xxx, xeme, xiii, xmas, xvii, xxii, xxiv, xyst, xebec, xenia, xenic,
        xenon, xenyl, xeres, xeric, xerif, xerox, xviii, xxiii, xylan, xylem, xylic, xylol, xylyl, xyris, xysts, xebecs,
        xenium, xenomi, xenons, xeriff, xmases, xylate, xylems, xylene, xylite, xyloid, xylose, xyster, xystus, xanthic,
        xanthin, xenylic, xeronic, xerosis, xeroxed, xeroxes, xiphias, xiphius, xiphoid, xiphura, xylenol, xyletic,
        xylidic,xylitol, xylogen, xysters, xanthate, xanthian, xanthide, xanthine, xanthium, xanthoma, xanthose,
        xanthous, xenogamy,xenolith, xenotime, xenurine, xeraphim, xeronate, xeroxing, xiphioid, xiphodon, xiphoids,
        xylamide, xylidine,xylitone, xylocopa, xyloidin, xylology, xylonite, xylorcin, xylotile, xylotomy, xylotrya,
        xylylene, xystarch, xanthates, xanthidia, xanthippe, xanthogen, xanthosis, xenelasia, xenocryst, xenodochy,
        xenograft, xenoliths,xenomania, xenophobe, xeroderma, xerophagy, xerophyte, xiphidium, xiphosura, xylindein,
        xylograph, xylophaga,xylophone, xylostein, xanthamide, xanthidium, xanthinine, xanthopous, xenolithic,
        xenophobes, xenophobia, xenophobic, xerography, xiphoidian, xiphosuran, xylanthrax, xylography, xylophagan,
        xylophilan, xylophones, xylotomist, xylotomous,  xanthelasma, xanthochroi, xanthogenic, xanthophane,
        xanthophyll, xanthorhiza, xanthorhoea, xanthoxylum, xenobiology, xenodochium, xenogenesis, xenogenetic,
        xerographic, xerophilous, xiphisterna, xylocarpous, xylographer, xylographic, xylophagous, xylophilous,
        xylophonist, xyloplastic, xyloquinone, xyridaceous, xanthochroic, xanthochroid, xanthogenate, xanthomatous,
        xanthoxylene, xenopterygii, xerophthalmy, xiphiplastra, xiphisternum, xylobalsamum, xylophagides, xylophonists,
        xanthocarpous, xanthochroism, xanthodontous, xanthoproteic, xanthoprotein, xanthopuccine, xanthorhamnin,
        xenobiologies, xerophthalmia, xiphiplastron, xiphophyllous, xylographical, xanthomelanous, xanthospermous,
        """
 
trie = Trie()
 
trie.add_multi(words)
print trie.add('xyj')
print trie.contains('xyj')
print trie.find('xy')