Получить максимальное количество конечных слов в пути для всех путей в Trie - PullRequest
Новая
       15

Получить максимальное количество конечных слов в пути для всех путей в Trie

0 голосов
/ 20 мая 2019

Рассмотрим следующие слова: 

'a', 'ab', 'abcd', 'b', 'bcd'

Добавление их в Trie приведет к следующему представлению со звездами, означающими, что узел является конечным словом: 

              root 
              / \
            *a  *b
            /     \
          *b       c
          /         \
         c          *d
        /
      *d

В этом примере у нас есть два пути, и максимальное количество конечных слов в любом пути равно 3 (a, ab, abcd). Как бы вы выполнили DFS, чтобы получить максимум?

Вот мой код для Trie: 

class TrieNode:

    def __init__(self):
        self.children = dict()
        self.end_word = 0

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key):
        current = self.root
        for char in key:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_word += 1

Ответы [ 2 ]

1 голос
/ 20 мая 2019

Вы должны добавить метод в свой TrieNode, если я хорошо понял ваш вопрос, вы хотите этот трие: 

          root 
          / \
        *a  *b
        /     \
      *b       c
      / \       \
     c  *d      *d
    /   /
  *d   *e

Для возврата 4 (a, ab, abd, abde)

Вы можете сделать это рекурсивно: 

class TrieNode:

    def __init__(self):
        self.children = dict()
        self.end_word = 0

    def count_end_words(self):
        if self.children:
            return self.end_word + max(child.count_end_words() for child in self.children.values())
        return self.end_word

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key):
        current = self.root
        for char in key:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_word += 1

    def max_path_count_end_words(self):
        return self.root.count_end_words()

root = Trie()
for word in ('a', 'ab', 'abcd', 'b', 'bcd', 'abd', 'abde'):
     root.insert(word)

print(root.max_path_count_end_words()) # returns 4

Как уже упоминалось в комментарии, вы можете избежать создания класса TrieNode, это способ сделать это: 

class Trie:

    def __init__(self):
        self.children = dict()
        self.is_end_word = False

    def insert(self, key):
        current = self
        if not key:
            return
        if len(key) == 1:
            self.is_end_word = True
        char  = key[0]
        if char not in current.children:
            self.children[char] = Trie()
        return self.children[char].insert(key[1:])

    def max_path_count_end_words(self):
        if self.children:
            return self.is_end_word + max(child.max_path_count_end_words() for child in self.children.values())
        return self.is_end_word

root = Trie()
for word in ('a', 'ab', 'abcd', 'b', 'bcd', 'abd', 'abde'):
     root.insert(word)

print(root.max_path_count_end_words()) # returns 4
0 голосов
/ 20 мая 2019

Вы можете добавить метод в класс TrieNode, который будет возвращать, является ли это end_word плюс сумма вызова одного и того же метода для всех дочерних элементов: 

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.end_word = 0
    def word_count(self):
        return self.end_word + sum([word_count() for c in self.children.values() ])

Чтобы использовать это: 

t = Trie()
for w in ('a', 'ab', 'abcd', 'b', 'bcd'):
    t.insert(w)

t.root.word_count()
# 5

Чтобы найти максимум, просто назовите его на всех корнях детей и сравните: 

max(branch.words() for branch in t.root.children.values())
# 3
...