Задача о создании рекурсивного диктата в python - PullRequest
Новая
       3

Задача о создании рекурсивного диктата в python

2 голосов
/ 19 февраля 2020

Я видел этот фрагмент кода онлайн: 

class StreamChecker(object):
    def __init__(self, words):
        """
        :type words: List[str]
        """
        print(words)
        self.waitlist = []
        self.trie = dict()
        for word in words:
            temp_dict = self.trie
            for letter in word:
                temp_dict = temp_dict.setdefault(letter, dict())

            temp_dict['#'] = '#'

if __name__ == '__main__':
    a = StreamChecker(['abc', 'wef', 'ykj'])
    print(a.trie)

После инициализации print self.trie получает {'a': {'b': {'c': {'#': '#'}}}, 'w': {'e': {'f': {'#': '#'}}}, 'y': {'k': {'j': {'#': '#'}}}}

Я запутался в этой строке 'temp_dict = temp_dict.setdefault(letter, dict())' в код. Поскольку каждый раз, когда setdefault возвращает пустой диктант {}, почему self.trie изменяется каждый раз, поскольку setdefault используется только для пустого дикта? Насколько я понимаю, self.trie будет меняться только один раз для каждого word, а self.trie должно быть похоже на {'a': {}, 'w': {}, 'y': {}}

Может кто-нибудь объяснить это мне? Спасибо

1 Ответ

4 голосов
/ 19 февраля 2020 
>>> help(dict.setdefault)
setdefault(self, key, default=None, /)
    Insert key with a value of default if key is not in the dictionary.

    Return the value for key if key is in the dictionary, else default.

Один пустой диктант не обязательно совпадает с объектом другого пустого диктанта. Происходит следующее: строка 

temp_dict = temp_dict.setdefault(letter, dict())

сначала добавляет новый ключ к текущему temp_dict (с соответствующим значением, являющимся пустым диктом), а затем возвращает ссылку на этот новый добавленная стоимость . Когда он запускается в l oop, он заканчивает тем, что рекурсивно добавляет новые словари к тому, чем был оригинал (то есть self.trie).

Поскольку вложенный dict, который мы модифицируем, содержится в пределах self.trie мы можем видеть наше изменение, отраженное в self.trie.

Это может помочь разложить это утверждение: 

temp_dict = temp_dict.setdefault(letter, dict())

на следующее: 

if letter not in temp_dict:
    temp_dict[letter] = dict()  # create a new dict, and put it inside the current dict
temp_dict = temp_dict[letter]   # jump inside the new dict that we just created, 
                                # or the existing dict that was there if it already existed.
...