2 Auto fill words

之前写的太复杂了，怪不得要挂。我在写一个简单一点的。

class node:
    def __init__(self):
        self.children = {}
        self.is_word = False

    # here is the magic
    def __repr__(self):
        return repr(self.children)


class Trie:
    def __init__(self, words):
        self.root = node()
        for w in words:
            self.add(w)

    def add(self, word):
        # add word to Trie
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = node()
            cur = cur.children[c]
        cur.is_word = True

    def find(self, prefix):

        # search in trie to the last char in prefix
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return []
            cur = cur.children[c]

        # traverse the sub tree return all suffix
        s = [(cur, '')]
        res = []
        while s:
            node, w = s.pop()
            if node.is_word:
                    res.append(w)
            for k in node.children:
                s.append((node.children[k], w+k))
        return [prefix + suf for suf in res]

words = ['app', 'apple', 'abc']
t = Trie(words)
print(t.root)
ans = t.find('a')
print(ans)

Implement a auto fill class. It will take a word dictionary for init. then it will auto fill the word you are entered. You can understand this by looking at my code.

# word = ['app', 'apple', 'application', 'appeal', 'ape', approve', 'apply', 'applicant']

class word(object):

    def __init__(self):
        self.dic = {}
        self.isword = False

class Solution(object):

    def __init__(self, words):
        self.word_freq = {}
        self.trie = None
        self.build_freq(words)
        self.build_trie(words)

    def build_freq(self, words):
        for w in words:
            self.word_freq[w] = 0

    def build_trie(self, words):
        trie = word()
        for i in words:
            tmp = trie
            for c in i:
                if c not in tmp.dic:
                    tmp.dic[c] = word()
                tmp = tmp.dic[c]
            tmp.isword = True
        self.trie = trie

    def get_words(self, prefix):
        res = []
        tmp = self.trie
        cur = prefix
        s = [tmp]

        # search in the trie untill finish prefix
        for c in prefix:
            if c not in tmp.dic:
                return []
            else:
                tmp = tmp.dic[c]

        if tmp.isword:
            res.append(res)

        # dfs the rest trie to find all the words start from this prefix
        self.dfs(tmp, prefix, res)

        # sorted res based on search times
        res = self.sort_helper(res)

        return res

    def pick(self, word):
        self.word_freq[word] += 1

    def sort_helper(self, words):
        count = [self.word_freq[word] for word in words]
        tmp = zip(count, words)
        res = sorted(tmp, key = lambda x: x[0])
        res = [i[1] for i in res]
        return res[::-1]

    def dfs(self, trieNode, cur, res):
        # if it is a word
        if trieNode.isword:
            res.append(cur)

        # No children for the node
        if not trieNode.dic:
            return

        # Go through all the keys to find the words.
        for key in trieNode.dic.keys():
            self.dfs(trieNode.dic[key], cur+key, res)


words = ['app', 'apple', 'application', 'appeal', 'ape', 'approve', 'apply', 'applicant', 'age', 'add', 'average', 'boy', 'bat']


s = Solution(words)
# first we get suggestuon for prefix ap
print s.get_words('ap')
# then we get suggestion for prefix b
print s.get_words('b')
# we decided to pick bat as our input
s.pick('bat')
# next time b will be ranked higher
print s.get_words('b')
s.pick('appeal')
print s.get_words('a')