Ex23 LMPTHW confusion about find_part

So I thought I had my find_partial working, and after re-reading the instructions, I’m a bit confused. My method works for finding something like ‘apx’ in a set with apple and ape in it, it will return those partial matches, if I ask it to find partial for ‘appl’ it will give me apple, not ape… I think I have it set up to stop once a leaf node is reached and there are no more relevant branches.
So question is, when I ask it to find partial match for ‘appl’ and, I have ‘ax’ in my tree: You want it to return ‘ax’ because it is the shortest one that matches part of the beginning of K?

Here’s my find_partial that returns first relevant node that contains branches that will hold values I’m looking for:

def find_any_partial(self, key, node=None, i=0, temp=None):
        if i == len(key):
            return temp
        else:
            if node.key == key[i]:
                i += 1
                return self.find_any_partial(key, node.eq, i, temp=node)
            elif node.key < key[i] and node.high:
                #print("go higher")
                return self.find_any_partial(key, node.high, i, temp=temp)
            else:
                if node.low:
                    #print("go lower")
                    return self.find_any_partial(key, node.low, i, temp=temp)
        return temp

IIRC I also had a problem with the concept of “partial”. I think it can be anything you define, just be consistent and document it. There’s also the problem that “partial” has a couple of possible meanings. You can mean “find the shortest partial match” but that’s always the matching first letter, since 1 character matching is the shortest. So that leaves longest common match.

I believe what I did is write a function that finds all the common matching beginnings, and puts them in a list, then callers can figure out if they want the shortest or longest.

1 Like