10815 - Andy's First Dictionary

[kissu parina]

easy problem...just keep in mind that
andy's-->>
andy
s
not andys.....

[cool]

can any one help me please

i am getting TLE

[plamplam]

Use a faster sorting algorithm (I think you are using bubble-sort) to sort the words in dictionary order. I used qsort to get AC in 0.115 seconds. Good luck.

[AbdoAdel]

Hi, this is my first post here
im getting a WA
this is my code :

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

void parseLine(const string& line, set<string>& words);
string removePunctAndConvertToLowerCase(const string& word);

int main() {
	string line;
	set<string> words;
	while (getline(cin, line))
		if (line != "")
			parseLine(line, words);
	for (set<string>::iterator it = words.begin(); it != words.end(); it++)
		cout << (*it) << endl;
	return 0;
}

void parseLine(const string& line, set<string>& words) {
	stringstream ss(stringstream::in | stringstream::out);
	ss << line;
	while (!ss.eof()) {
		string word;
		ss >> word;
		word = removePunctAndConvertToLowerCase(word);
		if (word != "" && words.find(word) == words.end())
			words.insert(word);
	}
}

string removePunctAndConvertToLowerCase(const string& word) {
	string tmp;
	for (int i = 0; i < (int) word.length(); i++) {
		if (isalpha(word[i]))
			tmp += tolower(word[i]);
	}
	return tmp;
}

General idea: i read a string containing one line, if that line is not empty, then ( parseLine ) parses it to words using string streams, removes punctuation and converts to lower case form and then check if it is not listed before
I would be very thankful if some one helped

[Joarder]

Why my code getting WA...???
Plz.... Someone Cheak it...
or Give me some test cases...
here is my code....

/*
* File: 10815 - Andy's First Dictionary.cpp
* Tag: String
* http://uva.onlinejudge.org/external/108/10815.html


* Runtime:
* Author: Shoshi
* Created on November 28, 2011, 9:00 PM
*/

#pragma warning (disable : 4786)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#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>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

using namespace std;

int main() {
//freopen("10815 - Andy's First Dictionary_in.txt", "r", stdin);
map<string,bool>m;
map<string,bool>::iterator it;
string str,str1;
int l,i;
while(cin>>str) {
l=str.length();
str1.clear();
for(i=0;i<l;i++) {
if((str>='A' && str<='Z') || (str>='a' && str<='z') || (str>='0' && str<='9')) {
str=tolower(str);
str1+=str;
}
else {
str.erase(i,1);
i--;
l--;
if(!str1.empty()) {
m[str1]=true;
str1.clear();
}
}
}
if(!str1.empty()) {
m[str1]=true;
str1.clear();
}
}
for(it=m.begin();it!=m.end();it++)
cout<<(*it).first<<endl;
return 0;
}

[sith]

Hello

Why my solution is wrong?

Code: Select all

class Main {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        try {
            Set<String> result = new HashSet<String>();
            while ((line = reader.readLine()) != null) {

                StringTokenizer tokenizer = new StringTokenizer(line, " !\"#$%&'()*+,-./0123456789:;<=>?@[]^_`{|}~");
                while (tokenizer.hasMoreTokens()) {
                    result.add(tokenizer.nextToken().toLowerCase());
                }
            }
            String[] words = result.toArray(new String[result.size()]);
            Arrays.sort(words);

            for (String word : words) {
                System.out.println(word);
            }
        }
        catch (IOException e) {

        }
    }
}

[brianfry713]

This code doesn't compile. Post the full code with the imports.

[sith]

Sorry. Here is the full code

Code: Select all

AC

[brianfry713]

For an input file containing:

Code: Select all

a\bc

My AC output is:

Code: Select all

a
bc

I used the c function isalpha().

[sith]

Thanks, it works

[mgavin2]

Code: Select all

int main() {
	//freopen("10815 - Andy's First Dictionary_in.txt", "r", stdin);
	map<string,bool>m;
	map<string,bool>::iterator it;
	string str,str1;
	int l,i;
	while(cin>>str) {
		l=str.length();
		str1.clear();
		for(i=0;i<l;i++) {
			if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z') || (str[i]>='0' && str[i]<='9')) {
				str[i]=tolower(str[i]);
				str1+=str[i];
			}
			else {
				str.erase(i,1);
				i--;
				l--;
				if(!str1.empty()) {
					m[str1]=true;
					str1.clear();
				}
			}
		}
		if(!str1.empty()) {
			m[str1]=true;
			str1.clear();
		}
	}
	for(it=m.begin();it!=m.end();it++)
		cout<<(*it).first<<endl;
	return 0;
}

Ok, it seems like you try your best to pull out punctuation and sort that situation out. So with input like "help.me" you get help and me, but if you hit a word that's possessive, then you're screwed.

eg. It was the dog's job to bark at the mailman.

you would end up with the word "s" in your list... Perhaps you should try to filter out any one letter words that aren't A or I?

Also when you need a set of unique elements, just use the set datatype
eg.

Code: Select all

#include <set>
#include <string>
using std::set;
using std::string;
set<string> words;

try to find a resource to explain more about it

[mgavin2]

also perhaps contractions in words : http://en.wikipedia.org/wiki/Contraction_(grammar)

[mgavin2]

Nevermind. I don't think it matters. I think your problem is accepting characters of '0'-'9' when it says in the problem statement "a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered." ...

after trying to solve it now I'm stuck in WA too. WAwsome.

[uvasarker]

I am getting TLE help me.........please

Code: Select all

/* Removed */
Thanks guru (brianfry713).
I got AC

[brianfry713]

Try rewriting it without using strtok, just test each character to see if it's a-z or A-Z. Also try sorting directly instead of using a map. Your tolow function is also going to be slow.