1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#define MAX 26//字符集大小
typedef struct TrieNode
{
    int nCount;//记录该字符出现次数
    struct TrieNode* next[MAX];
}TrieNode;
 
TrieNode Memory[1000000];
int allocp=0;
 
/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
    *pRoot=NULL;
}
 
/*创建新结点*/
TrieNode* CreateTrieNode()
{
    int i;
    TrieNode *p;
    p=&Memory[allocp++];
    p->nCount=1;
    for(i=0;i<MAX;i++)
    {
        p->next[i]=NULL;
    }
    return p;
}
 
/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
    inti,k;
    TrieNode*p;
    if(!(p=*pRoot))
    {
        p=*pRoot=CreateTrieNode();
    }
    i=0;
    while(s[i])
    {
        k=s[i++]-'a';//确定branch
        if(!p->next[k])
            p->next[k]=CreateTrieNode();
                p->next[k]->nCount++;
        p=p->next[k];
    }
}
 
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
    TrieNode *p;
    int i,k;
    if(!(p=*pRoot))
    {
        return0;
    }
    i=0;
    while(s[i])
    {
        k=s[i++]-'a';
        if(p->next[k]==NULL) return 0;
        p=p->next[k];
    }
    return p->nCount;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

""" Tries in python
Methods -  insert_key(k, v)
           has_key(k)
           retrie_val(k)
           start_with_prefix(prefix)
"""


def _get_child_branches(trie):
    """
    Helper method for getting branches
    """
    return trie[1:]


def _get_child_branch(trie, c):
    """
    Get branch matching the character
    """
    for branch in _get_child_branches(trie):
        if branch[0] == c:
            return branch

    return None


def _retrive_branch(k, trie):
    """
    Get branch matching the key word
    """
    if not k:
        return None

    for c in k:
        child_branch = _get_child_branch(trie, c)
        if not child_branch:
            return None
        trie = child_branch

    return trie


def _is_trie_bucket(bucket):
    if len(bucket) != 2:
        return False

    return type(bucket[1]) is tuple


def _get_bucket_key(bucket):
    if not _is_trie_bucket(bucket):
        return None

    return bucket[1][0]


def has_key(k, trie):
    """
    Check if trie contain the key word
    """
    return _retrive_branch(k, trie) is not None


def retrie_val(k, trie):
    key_tuple = _retrive_branch(k, trie)
    if not key_tuple:
        return None

    return key_tuple[1]


def insert_key(key, v, trie):
    """
    Insert a (key, value) pair into trie
    """
    if not key or has_key(key, trie):
        return

    for char in key:
        branch = _get_child_branch(trie, char)
        if not branch:
            new_branch = [char]
            trie.append(new_branch)
            trie = new_branch
        else:
            trie = branch
    trie.append((key, v))


def start_with_prefix(prefix, trie):
    """
    Find words start with prefix
    """
    branch = _retrive_branch(prefix, trie)
    if not branch:
        return []

    prefix_list = []
    q = branch[1:]
    while q:
        curr_branch = q.pop(0)
        if _is_trie_bucket(curr_branch):
            prefix_list.append(_get_bucket_key(curr_branch))
        else:
            q.extend(curr_branch[1:])

    return prefix_list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

trie = [[]]
states = """
            Alabama
            Alaska
            Arizona
            Arkansas
            California
            Colorado
            Connecticu
            Hawaii
            Idaho
            Illinois
            Indiana
            Maine
            Maryland
            Massachusetts
            Michigan
            Minnesota
            Mississippi
            Missouri
            Montana
"""
states_list = [w.strip().lower() for w in states.splitlines() if w]
for state in states_list:
    insert_key(state, True, trie)
print start_with_prefix("new", trie)