[python3] list vs. deque performance

Question [lc 1032]:

Implement the StreamChecker class as follows:
StreamChecker(words): Constructor, init the data structure with the given words.
query(letter): returns true if and only if for some k >= 1,
the last k characters queried (in order from oldest to newest, including this letter just queried)
spell one of the words in the given list.

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a'); // return false
streamChecker.query('b'); // return false
streamChecker.query('c'); // return false
streamChecker.query('d'); // return true, because 'cd' is in the wordlist
streamChecker.query('e'); // return false
streamChecker.query('f'); // return true, because 'f' is in the wordlist
streamChecker.query('g'); // return false
streamChecker.query('h'); // return false
streamChecker.query('i'); // return false
streamChecker.query('j'); // return false
streamChecker.query('k'); // return false
streamChecker.query('l'); // return true, because 'kl' is in the wordlist

Note:
1 <= words.length <= 2000
1 <= words[i].length <= 2000
Words will only consist of lowercase English letters.
Queries will only consist of lowercase English letters.
The number of queries is at most 40000.

Solve:

It's a trie problem. The thought should focus on query.

Thoughts:

• How to preserve the previous input state?
  stack
• Could backtrace be faster?
  Yes, only if the words last character being input could consider a hit.
  Thus should build a reverse trie.
• Tests can up to thousands thus query would be called about that much, Thus the stack used to preserve records could be large enough to trigger a realloc, which is SLOW(copy existing values to new memory address). In Python, instead of using list(which act like C++ vector), use deque to prevent realloc system call. Ref: https://stackoverflow.com/a/23487658

from collections import deque

class StreamChecker:
    def __init__(self, words: List[str]):
        self.trie = {}
        self.stack = deque()

        for word in set(words):
            node = self.trie

            for c in word[::-1]:
                if c not  in node:
                    node[c] = {}
                node = node[c]

            node[None] = None

    def query(self, letter: str) -> bool:
        self.stack.appendleft(letter)

        node = self.trie

        for c in self.stack:
            if None in node:
                return True

            if c not in node:
                return False
            node = node[c]

        return None in node