1
\$\begingroup\$

Here is my code for this problem. Any bugs, performance in terms of algorithm time complexity, code style advice are appreciated.

This is a continued discussion from (Find smallest subset prefixes) and since it is new code, I post a new thread.

Problem:

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 since foo is prefix for foo (itself), prefix for foog and prefix for food (in other words, foo could "represent" longer string like foog and 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.

Source code:

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isEnd = False
    def insert(self, word):
        node = self
        for w in word:
            node = node.children[w]
        node.isEnd = True
    def find_prefix(self, prefix, result):
        if self.isEnd:
            result.append(''.join(prefix[:]))
            return
        for w, child_node in self.children.items():
            prefix.append(w)
            child_node.find_prefix(prefix, result)
            prefix.pop(-1)

if __name__ == "__main__":
    words = ['foo', 'foog', 'food', 'asdf']
    root = TrieNode()
    for w in words:
        root.insert(w)
    result = []
    root.find_prefix([], result)
    print result
\$\endgroup\$
  • 3
    \$\begingroup\$ You can use [os.path.commonprefix()]{docs.python.org/2/library/os.path.html) to find the common prefix of a list of words. \$\endgroup\$ – Laurent LAPORTE Dec 27 '16 at 8:06
  • \$\begingroup\$ @LaurentLAPORTE, thanks for the advice. My purpose of this thread is more to learn how to implement the method by myself. Your advice of my original question, -- any bugs, performance in terms of algorithm time complexity, code style advice are appreciated. :) \$\endgroup\$ – Lin Ma Dec 27 '16 at 20:32
3
\$\begingroup\$

PEP 8

You still haven't followed PEP 8. Please:

  • Install (for example) Pylint.
  • You can run it as pylint filename.py.
  • If you use Vim you can install syntastic and every time you save it will run either flake8 or pylint.
  • There are alternatives for other text editors please install one, it will save you time in the long run.

def main

You have used if __name__ == "__main__": which is good. It is even considered more idiomatic (see this answer under "An Even Better Way") to do this:

def main():
    words = ('foo', 'foog', 'food', 'asdf')
    root = TrieNode()
    for w in words:
        root.insert(w)
    result = []
    root.find_prefix([], result)
    print result

if __name__ == "__main__":
    main()

Immutability

You don't mutate words. I would turn it into a tuple.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice Dair, from performance (in terms of algorithm time complexity) perspective, do you have any better ideas than using Trie Tree? \$\endgroup\$ – Lin Ma Dec 27 '16 at 20:33
  • 1
    \$\begingroup\$ @LinMa: I'm not really an expert in this, but the Wikipedia article dedicated to Tries provides some discussion about use cases and alternatives. \$\endgroup\$ – Dair Dec 28 '16 at 1:33
  • \$\begingroup\$ It is ok Dair, I will keep the thread open for a few days to see if anyone else have good ideas. \$\endgroup\$ – Lin Ma Dec 30 '16 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.