Data Structure

HackerRank/Data Structures/No Prefix Set

Problem Summary

Given N strings. Each string contains only lowercase letters from a to j(both inclusive). The set of N strings is said to be “GOOD SET” if no string is prefix of another string. Else, it is “BAD SET”.
(If two strings are identical, they are considered prefixes of each other.)

Solution

We use trie to store the set of strings.
For each string s[i], we try to add it to the set. Apparently, we need to make sure that

  1. s[i] is not a prefix of s[0],s[1],… or s[i-1].
  2. s[j] is not a prefix of s[i], for any j, 0 ≤ j < i.

Code

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
class Trie
{
public:
	bool is_element;
	Trie *p[10];
	Trie()
	{
		is_element = false;
		memset(p,0,sizeof(p));
	}
	~Trie();
	
	bool add(string s);
};
bool Trie::add(string s)
{
	Trie *ch = this;
	for (int i = 0; i < s.length(); ++i)
	{
		int cur = s[i] - 'a';
		if (ch->p[cur] == NULL)
			ch->p[cur] = new Trie;
		else
			if (ch->p[cur]->is_element)
				return false;
		ch = ch->p[cur];
	}
	ch -> is_element = true;
	for (int i = 0; i < 10; ++i)
		if (ch->p[i] != NULL)
			return false;
	return true;
}
int main()
{
	int n;
	Trie *trie = new Trie;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		string s;
		cin>>s;
		if (!trie->add(s))
		{
			cout<<"BAD SET"<<endl<<s<<endl;
			return 0;
		}
	}
	cout<<"GOOD SET"<<endl;
	return 0;
}