Here is my code for this problem. Any bugs, performance in terms of algorithm time complexity, code style advice are appreciated.
The areas which I want to improve, but do not know how to improve are:
- I sort the strings by length and I'm not sure if it's a smarter idea not using sorting at all.
- I used a few set operations, which looks a bit ugly. I want to learn smarter ideas.
Given a set of strings, return the smallest subset that contains the longest possible prefixes for every string.
If the list is ['foo', 'foog', 'food', 'asdf'] return ['foo', 'asdf']
The return is
foo is prefix for
foo (itself), prefix for
foog and prefix for
food (in other words,
foo could "represent" longer string like
food). Output also contains
asdf because it is not prefix for any other words in the input list, so output itself.
The empty set is not a correct answer because it does not contain the longest possible prefixes.
from collections import defaultdict class TrieTreeNode: def __init__(self): self.children = defaultdict(TrieTreeNode) self.isEnd = False self.count = 0 def insert(self, word, result_set): node = self for i,w in enumerate(word): node = node.children[w] if node.isEnd: result_set[word[:i+1]].add(word) node.isEnd = True if __name__ == "__main__": words = ['foo', 'foog', 'food', 'asdf'] words_length =  sorted_words =  for w in words: words_length.append(len(w)) for t in sorted(zip(words_length, words)): sorted_words.append(t) result_set = defaultdict(set) root = TrieTreeNode() for w in sorted_words: root.insert(w, result_set) match_set = set() for k,v in result_set.items(): for i in v: match_set.add(i) unmatch_set = set(words) - match_set print unmatch_set | set(result_set.keys())