895 – Word Problem UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=836

Strings, ad hoc, input parsing, sstream.

How I did it

• I read the dictionary words inside a vector until I found “#”.
• I read the request queries until I found another “#”.(stringstream).
• I check word by word if  can I get the word from the dictionary.
• If a word can be formed increment a counter.
• Print the counter value.

Hints

• We can use a backtracking approach to check all the possible results.
• The input is not bigger.
• Read with getline and parse the input with sstream.

Code

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
using namespace std;
vector<string> dictionary;
vector<char> letter;
vector<int> status;
int cont;

void checkInput()
{
string current;
bool flag;
    for(int x=0; x<dictionary.size(); x++)
    {
        current = dictionary[x];
        status.assign(letter.size(), 0);
        for(int y=0; y<current.size(); y++)
        {
            flag  = false;
            for(int z=0; z<letter.size(); z++)
            {
                if(current[y] == letter[z] && status[z] == 0)
                {
                    status[z] = 1;
                    flag = true;
                    break;
                }
            }
            if(flag == false)
               break;
        }
        if(flag)
           cont++;
    }
}

int main()
{
string str;
char data;
stringstream ss;

while(getline(cin, str))
{
    if(str == "#")
       break;
    dictionary.push_back(str);
}
while(getline(cin,str))
{
    if(str == "#")
       break;
    stringstream ss;
    cont = 0;

    ss<<str;

    while(ss>>data)
        letter.push_back(data);

    //for(int c=0; c<dictionary.size(); c++)
    //    cout<<dictionary[c]<<" "<<endl;
    //cout<<endl;

    //for(int c=0; c<letter.size(); c++)
     //   cout<<"To->"<<letter[c]<<" ";
    //cout<<endl;

    checkInput();
    printf("%d\n", cont);
    letter.clear();
}
return 0;
}