SPOJ – PHONELST – Phone List

Arunima Mandal

Problem Link: https://www.spoj.com/problems/PHONELST/


Solution: This is a pretty great problem regarding applying Trie in the case of a numerical string. If your code is not executing, please take a good look at whether you are taking the index as s[i]-‘0’ instead of s[i]-‘a’. Since in most cases, the strings consist of alphabets, so in most cases in the Trie code template, we can write the index code as s[i]-‘a’ habitually.

Here the main trick is to sort the vector containing strings before inserting those into the Trie, to make sure we are marking the smaller words first. Otherwise, we will miss the smaller words, and that way the long words with the same prefix equal to the smaller words will go undetected.

Code:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[10]={};
    bool word=0;
};

bool insert(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'0';
        if(it->word==1) return 0;
        if(!it->child[ind]) it->child[ind]= new TrieNode();
        it=it->child[ind];
    }
    it->word=1;
    return 1;
}

int main()
{
    int t,n;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<string> v;
        string s;
        for(int i=0; i<n; i++)
        {
            cin>>s;
            v.push_back(s);
        }
        sort(v.begin(), v.end());

        TrieNode *root=new TrieNode();
        bool is_consistent=1;
        for(int i=0; i<n && is_consistent; i++)
        {
            is_consistent=insert(root, v[i]);
        }

        if(is_consistent) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

Leave a comment