LOJ 1129 - Consistency Checker
In this problem, you will be given T
testcases. The first line of each test case contains an integer n
. Following n
lines will contain a number of length 1-10
each. You are asked to check the consistency of the dataset. The consistency is, no number is a prefix of another number.
To recap, a substring of a string from its 0th
index is a prefix of that string. Like 123
is a prefix of 12345
, but 124
, 234
, or 132
is not.
This is a great problem to start Trie Data Structure if you haven't already.
Tries are an extremely special and useful data-structure that are based on the prefix of a string. They are used to represent the “Retrieval” of data.
Here are some resources to trie data structure you can understand and learn:-
Approach:
Atfirst, we create a trie for each new testcase. A single node of trie data structure will contain a boolean
variable and an array
of trie nodes of length 10
. The boolean variable will say if a string end on that node or not. The 10
size array will be enough for the next adjacent digit of the number because different digits can be atmost ten (0-9)
.
The best way to take input of the n
numbers for each testcase is as strings. Because trie deals with the prefix of a string. If we want to take n
numbers as integers, we can. Because integer
data type can hold between -2147483648
to +2147483647
which will be enough to hold an integer of length 1-10
. But still that won't be a smart approach.
So we simply take the n
input numbers as strings and insert into the trie. Once the trie is formed, we create a function isPrefix()
which will check if there is a single number prefix of another number or not in the trie. How will the function check? The function will traverse the trie, and if there is a single node which has the boolean variable value true
but more trie nodes emit from that node, this confirms that it is a prefix.
Example, if our trie consists of two numbers 123
and 12345
, at the node for digit 3
, there is a number ending but still more node coming out from it. So, this confirms that the dataset is not consistent.
Visualization-
//A trie with two strings inserted, "123" and "12345"
1(false)
\
2(false)
\
3(true) <-- ending of string "123" but not the leaf node!
\
4(false)
\
5(true) <-- ending of string "12345" and it is a leaf node
Lastly, after the answer is got, we delete the trie from the memory to avoid memory wastage in our program.
Try yourself before watching the code below.
C++:
#include<iostream>
#include<stdio.h>
using namespace std;
struct trie
{
bool endmark;
trie *arr[10];
trie()
{
endmark = 0;
for(int i=0; i<=9; i++)
{
arr[i] = NULL;
}
}
} * root;
void insert(char s[])
{
int n = 0;
for( ; s[n]; n++) {}
trie *curr = root;
for(int i=0; i<n; i++)
{
int x = int(s[i]-'0');
if(curr->arr[x]==NULL) curr->arr[x] = new trie();
curr = curr->arr[x];
}
curr->endmark = 1;
}
void del(trie* node)
{
for(int i=0; i<10; i++)
{
if(node->arr[i]!=NULL)
del(node->arr[i]);
}
delete(node);
}
bool isPrefix(trie *node)
{
for(int i=0; i<=9; i++)
{
if(node->arr[i]!=NULL)
{
if(node->endmark) return 1;
if(isPrefix(node->arr[i])) return 1;
}
}
return 0;
}
int main()
{
int t=0,tc=0;
scanf(" %d", &tc);
for(t=1; t<=tc; t++)
{
int i=0, j=0;
root = new trie();
int n;
scanf(" %d", &n);
char s[10];
while(n--)
{
scanf(" %s",&s[0]);
insert(s);
}
isPrefix(root)? printf("Case %d: NO\n",t) : printf("Case %d: YES\n",t);
del(root);
}
return 0;
}
Tutorial source