{"id":1775,"date":"2015-08-24T15:33:10","date_gmt":"2015-08-24T10:03:10","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=1775"},"modified":"2023-11-19T06:59:02","modified_gmt":"2023-11-19T06:59:02","slug":"trie-tree-practise-spoj-phonelst","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2015\/08\/24\/trie-tree-practise-spoj-phonelst\/","title":{"rendered":"Trie Tree Practise – SPOJ – PHONELST"},"content":{"rendered":"\n

Hello people..! In this post I will show you how to get started with solving Trie Tree based questions in competitive programming. Learning a data structure is different from solving competitive coding questions based on that data structure. In this post, I take up a very simple question so that your confidence is boosted.
We will look at the SPOJ problem – Phone List<\/a>. It is a very straight forward problem. Just so that you don’t need to go to SPOJ in a new tab, I’m putting the problem statement here.<\/p>\n\n\n\n

Problem Statement<\/h3>\n\n\n\n

Phone List Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let\u2019s say the phone catalogue listed these numbers:<\/p>\n\n\n\n

\u2022 Emergency 911<\/p>\n\n\n\n

\u2022 Alice 97 625 999<\/p>\n\n\n\n

\u2022 Bob 91 12 54 26<\/p>\n\n\n\n

In this case, it\u2019s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob\u2019s phone number. So this list would not be consistent.<\/p>\n\n\n\n

Input<\/strong><\/p>\n\n\n\n

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.<\/p>\n\n\n\n

Output<\/strong><\/p>\n\n\n\n

For each test case, output \u201cYES\u201d if the list is consistent, or \u201cNO\u201d otherwise.<\/p>\n\n\n\n

The Problem in terms of Trie Tree<\/h3>\n\n\n\n

We are supposed to check if any word is a prefix of any other or not. Now, there might be a hundred ways to solve this problem, but we will do this using a trie tree so that we can get confident in using the data structure, and so that we can attempt tougher ones based on a trie tree. All throughout my explanation, I will be referring to the implementation in my post on Trie Tree<\/a>.
What we will do to solve this problem is that, we will insert the words into the trie tree one-by-one, and we will check for the prefix word criteria as we are inserting. Now, there are 2 cases.<\/p>\n\n\n\n

Case – 1 – Prefix word is already inserted<\/h4>\n\n\n\n

This is the sample test case. Consider this test case –<\/p>\n\n\n

Input<\/div>
\nface
\nfacebook
\n<\/div><\/div>\n\n\n\n

So, what I said we will do is that, we will be inserting the words one-by-one. So, when we insert the word “face”, no problems occur. But while inserting the word “facebook”, we would travel to the nodes F \u2192 A \u2192 C \u2192 E. And at the node E, we would have some indication that this node is a leaf node, that is, some word ends here. In my implementation, this can be indicated by –<\/p>\n\n\n\n

\nif (temp->occurrences.size() == 0) {\n\t\/\/ not a leaf node\n} else {\n\t\/\/ a leaf node, thus this is\n\t\/\/ the end of the prefix word\n}\n<\/pre><\/pre>\n\n\n\n
If we encounter this situation, we know that the result will be NO.<\/p>\n\n\n\n
Case 2 – Prefix word is about to be inserted<\/h4>\n\n\n\n
This is just the opposite of the previous case, consider the test case –<\/p>\n\n\n
Input<\/div>
\nfacebook
\nface
\n<\/div><\/div>\n\n\n\n
We won’t have any issues while inserting “facebook”. But when inserting “face”, we traverse F \u2192 A \u2192 C \u2192 E. And in the end of insertion, we see that there is a child node to the node E. Which means that there is a bigger word which ends somewhere deep down the trie tree. Which means that we just inserted the prefix word. We could check this by traversing the children array –<\/p>\n\n\n\n
\nfor (i = 0; i &lt; ALPHABETS; ++i) {\n\tif (temp->children[i] != NULL) {\n\t\t\/\/ The newly inserted word is\n\t\t\/\/ prefix to another word\n\t}\n}\n<\/pre><\/pre>\n\n\n\n
In this case too, the answer would be a NO. For every other case, the answer would be a YES.<\/p>\n\n\n\n
So, try to code this problem. Take your code of the trie tree, remove the unnecessary things first, like the delete function or print function or any others which we won’t need. As far as I know, the insert function is all that you will need. And try to make the changes required for the test cases.
Your insert function could return a true or a false, depending on whether the insertion encountered a prefix test case or not. Take time to think about it and try to code it. If you get stuck, you can refer to my code below –<\/p>\n\n\n\n