Leetcode Python 208. Реализация дерева (префиксное дерево) - PullRequest
Новая
       49

Leetcode Python 208. Реализация дерева (префиксное дерево)

0 голосов
/ 28 октября 2018

Может кто-нибудь сказать, что не так с моим кодом, он проходит все тестовые случаи, кроме последнего, когда я загрузил конкретный тестовый пример, и ожидаемый и фактический выходные данные кажутся одинаковыми, вопрос https://leetcode.com/problems/implement-trie-prefix-tree/description/

Редактировать 1: Вот код: 

class Trie:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.data = None
    self.children = {}
    self.isWord = False

def insert(self, word):
    """
    Inserts a word into the trie.
    :type word: str
    :rtype: void
    """
    if len(word) == 0:
        return
    if word[0] not in self.children:
        self.children[word[0]] = Trie()
        self.insertHelper(word[1:], self.children[word[0]])
    else:
        self.insertHelper(word[1:], self.children[word[0]])

    if len(word) == 1:
        self.isWord = True

def insertHelper(self, word, trie):
    if len(word) == 0:
        return

    if word[0] not in trie.children:
        trie.children[word[0]] = Trie()
        trie.insertHelper(word[1:], trie.children[word[0]])
    else:
        trie.insertHelper(word[1:], trie.children[word[0]])

    if len(word) == 1:
        trie.isWord = True





def search(self, word):
    """
    Returns if the word is in the trie.
    :type word: str
    :rtype: bool
    """
    if len(word) == 1 and word[0] in self.children and self.isWord:
        return True
    elif len(word) == 0:
        return False

    if word[0] in self.children:
        return self.searchHelper(word[1:], self.children[word[0]])
    else:
        return False

def searchHelper(self, word, trie):
    if len(word) == 1 and word[0] in trie.children and trie.isWord:
        return True
    elif len(word) == 0:
        return False

    if word[0] in trie.children:
        return self.searchHelper(word[1:], trie.children[word[0]])
    else:
        return False



def startsWith(self, prefix):
    """
    Returns if there is any word in the trie that starts with the given prefix.
    :type prefix: str
    :rtype: bool
    """
    if len(prefix) == 0:
        return False
    if prefix[0] in self.children:
        return self.startsWithHelper(prefix[1:], self.children[prefix[0]])
    else:
        return False

def startsWithHelper(self, prefix, trie):
    if len(prefix) == 0:
        return True

    if prefix[0] in trie.children:
        return trie.startsWithHelper(prefix[1:], trie.children[prefix[0]])
    else:
        return False

Заранее спасибо.

1 Ответ

0 голосов
/ 29 октября 2018

Одна странность, которую я заметил, это передача пустого префикса в startsWith().Если этот метод смоделирован на методе Python str startswith(), то мы ожидаем True: 

>>> "apple".startswith("")
True
>>>

Но ваш Trie возвращает False в этой ситуации: 

>>> t = Trie()
>>> t.insert("apple")
>>> t.startsWith("")
False
>>>

Ниже я переделал ваш код, который я сделал в первую очередь, чтобы понять его, но я также обнаружил, что у вас были избыточности, в частности ваши функции Helper .Этот код исправляет причуду, упомянутую выше, и специфична для Python 3: 

class Trie:

    def __init__(self):
        self.children = {}
        self.isWord = False

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str (or list internally upon recursion)
        :rtype: None
        """

        if not word:
            return

        head, *tail = word

        if head not in self.children:
            self.children[head] = Trie()

        trie = self.children[head]

        if tail:
            trie.insert(tail)
        else:
            self.isWord = True

    def search(self, word):
        """
        Returns True if the word is in the trie.
        :type word: str (or list internally upon recursion)
        :rtype: bool
        """

        if not word:
            return False

        head, *tail = word

        if head in self.children:
            if not tail and self.isWord:
                return True

            return self.children[head].search(word[1:])

        return False

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str (or list internally upon recursion)
        :rtype: bool
        """

        if not prefix:
            return True

        head, *tail = prefix

        if head in self.children:
            return self.children[head].startsWith(tail)

        return False
...