I have list of string which are prefix list(assuming its huge in numbers), if I want to check for given name/string which longest prefix from prefix list will be match for this name/string. i.e. Prefix List:['good','goo','go'] Input: name:'goodboy' result: good

For small number of data in list, we can use normal Search/match techniques but for huge data, can someone please suggest how can i imporve.

CodePudding user response：

You can use a trie.

Here is an implementation:

class Trie(dict):
    def add(self, s):
        node = self
        for ch in s:
            if ch not in node:
                node[ch] = Trie() 
            node = node[ch]

    def findprefix(self, s):
        node = self
        for i, ch in enumerate(s):
            if ch not in node:
                return s[:i] 
            node = node[ch]
        
trie = Trie()
for s in ["good", "goo", "go"]:
    trie.add(s)
print(trie.findprefix("goodbye"))  # "good"