Trie with insert, search, and startsWith methods for lowercase strings
Assuming the next attribute of TrieNode is just a lookup for letters of the alphabet, you might be better off replacing it with a dictionary that maps letters of the alphabet to their next value. Something like:

class TrieNode(object):
    def __init__(self):
        self.next = {letter: ['!', None] for letter in string.ascii_lowercase}
        self.isWord = False




and now, rather than mucking around with ord() in your insert() and search() methods, you can use the characters directly. That won’t fundamentally change the complexity, but will make a small performance saving.

I think insert and search of a trie is O(key_length), so this is probably the sort of saving you need. You can’t change the complexity.



A few other small suggestions:


Comparisons to None should use foo is None and foo is not None, not direct equality.
Once you’re using the characters as keys in the next attribute, you’d be better of replacing those while i &lt; wordLength loops with something like for i, char in enumerate(word).
In general, PEP 8 convention is that Python variables are lowercase with underscores (e.g. is_word, starts_with), and only classes are camel case. (Although as @Graipher notes in the comments, camel case is specified for startsWith().)