Как изменяемый аргумент по умолчанию ломает Trie на LeetCode

Разбираем баг в задаче LeetCode Implement Trie: из-за изменяемого значения по умолчанию dict экземпляры делят состояние. Причина и исправление с None.

Задача LeetCode «Implement Trie (Prefix Tree)» кажется рядовой, пока не падает самый простой тест. Исполнитель создает новый объект, вызывает startsWith на "a" и ожидает false. Вместо этого приходит true, а печать структуры показывает данные, явно относящиеся к прошлому тесту. Ловушка не в самой логике три, а в конструкторе: изменяемый аргумент по умолчанию тихо делит состояние между экземплярами.

Триггер ошибки в коде

Сама логика префиксного дерева корректна, но инициализатор использует общий словарь в качестве значения по умолчанию. Это состояние «просачивается» между разными объектами и тестами.

from collections import deque

class PrefixTree:
    def __init__(self, branch_map = {}, label = '', terminal = False):
        self.branch_map = branch_map
        self.label = label
        self.terminal = terminal

    def __str__(self):
        s = ''
        s += self.label
        q = deque([])
        for ch in self.branch_map.values():
            q.append(ch)
        while q:
            n = q.popleft()
            s += n.label
            if n.terminal:
                s += 'T'
            for ch in n.branch_map.values():
                q.append(ch)
        return s

    def __repr__(self):
        return self.__str__()

    def child(self, val) -> "PrefixTree":
        return self.branch_map[val]

    def has(self, val) -> bool:
        return val in self.branch_map

    def mark(self) -> None:
        self.terminal = True

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if not node.has(ch):
                fresh = PrefixTree({}, ch, False)
                node.branch_map[ch] = fresh
            node = node.child(ch)
        node.mark()

    def search(self, word: str) -> bool:
        node = self
        for ch in word:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return node.terminal

    def startsWith(self, prefix: str) -> bool:
        # вывести self
        node = self
        for ch in prefix:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return True

Что на самом деле происходит

Минимальный пример делает проблему очевидной. Если передать dict как параметр по умолчанию, каждый новый экземпляр без явного аргумента будет использовать ровно тот же словарь.

class Holder:
    def __init__(self, payload={}):
        self.payload = payload
    def __repr__(self):
        return '{' + ','.join(f'{k}:{self.payload[k]}' for k in self.payload) + '}'
    def put(self, k, v):
        self.payload[k] = v

Попробуйте интерактивно — и вы увидите «перетекание» между независимыми созданиями объекта:

>>> h1 = Holder()
>>> h1
{}
>>> h1.put(1, 2)
>>> h1
{1:2}
>>> h2 = Holder()
>>> h2
{1:2}

Каждый экземпляр, созданный без явного payload, делит один и тот же объект «изначально {}», который затем мутирует. То же самое происходит и с отображением потомков в trie: вставка в одном месте меняет структуру для других экземпляров. Поэтому тест, который конструирует новый Trie и вызывает startsWith, может «увидеть» слова вроде app и apple, оставшиеся с прошлого запуска.

Правило: не используйте изменяемые значения в параметрах по умолчанию, если только вы точно не понимаете, что делаете.

Исправление и корректный код

Безопасный шаблон — ставить по умолчанию None и создавать новый словарь внутри инициализатора. Так каждый экземпляр получает собственное отображение.

class Holder:
    def __init__(self, payload=None):
        self.payload = {} if payload is None else payload
    def __repr__(self):
        return '{' + ','.join(f'{k}:{self.payload[k]}' for k in self.payload) + '}'
    def put(self, k, v):
        self.payload[k] = v

Применительно к trie:

from collections import deque

class PrefixTreeFixed:
    def __init__(self, branch_map=None, label='', terminal=False):
        self.branch_map = {} if branch_map is None else branch_map
        self.label = label
        self.terminal = terminal

    def __str__(self):
        s = ''
        s += self.label
        q = deque([])
        for ch in self.branch_map.values():
            q.append(ch)
        while q:
            n = q.popleft()
            s += n.label
            if n.terminal:
                s += 'T'
            for ch in n.branch_map.values():
                q.append(ch)
        return s

    def __repr__(self):
        return self.__str__()

    def child(self, val) -> "PrefixTreeFixed":
        return self.branch_map[val]

    def has(self, val) -> bool:
        return val in self.branch_map

    def mark(self) -> None:
        self.terminal = True

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if not node.has(ch):
                fresh = PrefixTreeFixed({}, ch, False)
                node.branch_map[ch] = fresh
            node = node.child(ch)
        node.mark()

    def search(self, word: str) -> bool:
        node = self
        for ch in word:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return node.terminal

    def startsWith(self, prefix: str) -> bool:
        node = self
        for ch in prefix:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return True

Почему это важно

Скрытое общее состояние порождает «гуляющие» баги: в одном режиме запуск выглядит нормальным, а в другом все падает, потому что прошлые операции изменили якобы пустую структуру. В окружениях, где последовательно прогоняются несколько кейсов, такая утечка проявляется как непоследовательные результаты и странные выводы, где видно данные из предыдущих тестов. Выделение нового словаря на экземпляр возвращает изоляцию и делает поведение детерминированным.

Выводы

Если наблюдаете загадочное «заражение» тестов при работе с классами, принимающими контейнеры в конструкторе, проверьте параметры по умолчанию на изменяемость. Замените их на None и создавайте новые объекты внутри инициализатора. Эта небольшая правка не позволяет состоянию перетекать между экземплярами, держит структуры данных независимыми и убирает ложные срабатывания вроде startsWith, возвращающего true там, где в этом тесте ничего не вставлялось.