Posted in C++

Word List – IARCS Problem Archive

Problem Link.

This is a nice excercise on the C++ STL Library. For those who aren’t familiar with it (for otherwise you wouldn’t be reading this article) , the best data structure for this will be the set. The set is just like any mathematical set – where you have just one copy of elements, that is even if you insert duplicate elements, it will automatically rectify the duplicacy for you.And it also automatically iterates over elements in a sorted order (to be specific they are saved as binary search trees), so you will never have to worry about sorting the words.

It is a useful data structure for several other problems also. Our strategy will be straight forward. As the constraints say there are at most 1000 elements (words). The cost of inserting in a set will take at most O(log N) operations and separating the words can be done in O(n). So our total complexity turns to be  O(n + nlog n) = O(n log N).

All that’s left is to code – and get the AC.

PS – I’m bad at analysing complexities.

The Code —- Warning do Not look at this before you have tried the problem yourself.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    set <string> s;
    string word;
    char buffer[100];
    int n,i,j;
    cin>>n;
    cin.getline(buffer,100,'\n');
    for(i=0;i<n;i++)
    {
        cin.getline(buffer,100,'\n');
        word.clear();
        for(j=0;buffer[j]!='\0';j++)
        {
            if(buffer[j]>='a'&& buffer[j]<='z')
            {
                word+=buffer[j];
            }
            else if(buffer[j]>='A' && buffer[j]<='Z')
            {
                buffer[j]=buffer[j]-'A'+'a';
                word+=buffer[j];
            }
            else if(buffer[j]=='\''){}
            else
            {
                if(word.empty()){}
                else
                {
                    s.insert(word);
                    word.clear();
                }
            }
        }
        if(word.empty()){}
        else
        {
            s.insert(word);
            word.clear();
        }
    }
    cout<<s.size()<<"\n";
    for(set<string>::iterator itr =s.begin(); itr!=s.end(); itr++)
    {
        cout<<*itr<<"\n";
    }
    return 0;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s