UVa : 642 (Word Amalgamation)


Title : Word Amalgamation

Link : http://uva.onlinejudge.org/external/6/642.html

Tricky Lines :

  1. Note that the sentinel XXXXXX contains uppercase X‘s
  2. The dictionary is not necessarily in sorted order

Analysis :

  1. take all the dictionary words in a char array or string array
  2. sort the string array by word
  3. take a scramble word and loop through the dictionary words
  4. if scramble word can made from a particular dictionary word then output it
  5. two words can be made from each other, if there sorted version are same
    suppose, scramble word = ooslhc (sorted : chloos)
    dictionary word = school (sorted : chloos)

Runtime : 0.016s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;


int main ()
{
    string dictionary [100 + 5];
    string scramble;
    string end = "XXXXXX";

    int dic_len = 0;

    while ( cin >> dictionary [dic_len] && dictionary [dic_len] != end ) dic_len++;

    sort (dictionary, dictionary + dic_len);

    while ( cin >> scramble && scramble != end ) {
        sort (scramble.begin (), scramble.end ());
        bool print_one = false;
        for ( int i = 0; i < dic_len; i++ ) {
            string temp = dictionary [i];
            sort (temp.begin (), temp.end ());
            if ( scramble == temp ) {
                cout << dictionary [i] << endl;
                print_one = true;
            }
        }

        if ( !print_one ) cout << "NOT A VALID WORD" << endl;
        cout << "******" << endl;
    }

	return 0;
}

// @END_OF_SOURCE_CODE
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