Trying to build trie with classes in python - strange behavior

Question

I'm trying to implement trie in python. I'm using dictionaries+classes instead of lists (I know it's not optimal, but I'm just trying to make it work at all).

After debugging I found out that each layer has all letters in dictionary. I cannot understand why.

Here is my code (implementation is 100% most basic, straightforward):

class lttr:
    finish = 0
    pointers = {}  #for letters to reference class instance

eps = lttr()

def add(word):
    global eps
    last = eps
    for ind,x in enumerate(word):
        if last.pointers.get(x,None):
            last = last.pointers[x]
        else:
            last.pointers[x] = lttr()
            last=last.pointers[x]
    last.finish=1

def lookup(word):
    global eps
    last=eps
    for ind,x in enumerate(word):
        if last.pointers.get(x,None):
            last=last.pointers[x]
        else:
            return False
    return bool(last.finish)

add("pear")
print lookup("ar")  #prints True ... but why?

Answer 1

I'm guessing you intended for each individual lttr instance to have its own unique values for finish and pointers. In which case, you need to declare them as attributes of self inside __init__, rather than just defining them at the class scope.

class lttr:
    def __init__(self):
        self.finish = 0
        self.pointers = {}  #for letters to reference class instance

Now your script will print False as expected.