标准trie应用之判断一堆单词中有没有某一个单词是另一个单词的前缀

缘起

题目:

给你N个单词, 每个单词长度均不超过L，要你判断有没有某个单词是另一个单词的前缀这种现象发生.

分析

容易想到的思路就是如下三种

  1. 逐个比较，就是抽取两个单词，看看短的单词是不是长的单词的前缀，这种算法的时间复杂度是O(L*N^2)的，要死人的
  2. Hash. 也就是将所有单词的前缀写入哈希表（构建哈希表的时间复杂度是O(L*N)(乘以L是因为每个单词有L种前缀)），然后查找的时间复杂度是O(N), 所以总的时间复杂度是O(L*N)
  3. trie. 构造trie的复杂度是 O(N*L), 构造的过程中就能发现.

这里显然选择trie.

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
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define LOCAL

const int SIZE = 26;

typedef struct TrieNode
{
	int ch;
	bool end;
	TrieNode *next[SIZE];
	TrieNode(int ch=0):ch(ch),end(false) {memset(next, 0, sizeof(next));}
}TrieNode,*Trie;

void init(Trie &root) {root = new TrieNode;}

bool insert(Trie root, char *key)
{
	Trie p = root;
	int i = 0;
	while(key[i])
	{
		if (!p->next[key[i]-'a'])
		{
			p->next[key[i]-'a'] = new TrieNode(key[i]);
		}
		if (p->end) return true; // 如果当前节点是某个单词的结束的话, 则说明存在前缀问题
		p = p->next[key[i++]-'a'];
	}
	if (p->end) return true;
	p->end =  true;
	return false;
}

void del(Trie &root)
{
	if (!root) return;
	for (int i = 0; i<SIZE; i++)del(root->next[i]);
	delete root;
	root = 0;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Trie root = 0;
	init(root);
	char key[15];
	while(~scanf("%s", key))
	{
		if(insert(root, key))
		{
			puts("存在一个单词是另一个单词的前缀的情况.");
			del(root);
			return 0;
		}
	}
	puts("不存在一个单词是另一个单词的前缀的情况.");
	del(root);
	return 0;
}
/*
测试数据
haning hann hanin
*/