195 - Anagram
Moderator: Board moderators
-
- New poster
- Posts: 32
- Joined: Tue Feb 13, 2007 1:31 pm
Re: 195: anagram, wrong answer
some info about Problem 195
1.there is no blank between characters in the word.
2.the length about 100 characters is enough
3.alphabet order is A -> a -> B -> b -> C -> c ..... -> Y -> y -> Z -> z
4.Problem 146 is similar with Problem 195, but test cases in Problem 146 are weak, and some wrong algorithms(I have tested) also got Accepted.
So make sure your algorithm is correct.
Hope it helps.
1.there is no blank between characters in the word.
2.the length about 100 characters is enough
3.alphabet order is A -> a -> B -> b -> C -> c ..... -> Y -> y -> Z -> z
4.Problem 146 is similar with Problem 195, but test cases in Problem 146 are weak, and some wrong algorithms(I have tested) also got Accepted.
So make sure your algorithm is correct.
Hope it helps.
Re: 195: anagram, wrong answer
I think my algorithm is right,but I got WA.
Could someone tell me why?please
Could someone tell me why?please
Code: Select all
AC
Last edited by a13032002 on Fri Apr 02, 2010 5:00 pm, edited 1 time in total.
Re: 195: anagram, wrong answer
I think your compare function is not correct..
m=i>='a'&&i<='a'?i-'a':i-'A';
Shouldn't this be..
m= i>='a' && i <= 'z' ? i - 'a' : i - 'A'
m=i>='a'&&i<='a'?i-'a':i-'A';
Shouldn't this be..
m= i>='a' && i <= 'z' ? i - 'a' : i - 'A'
Re: 195: anagram, wrong answer
I got AC.Thank you!helloneo wrote:I think your compare function is not correct..
m=i>='a'&&i<='a'?i-'a':i-'A';
Shouldn't this be..
m= i>='a' && i <= 'z' ? i - 'a' : i - 'A'
That was a stupid mistake
Re: 195: anagram, wrong answer
What's problem in my Code .PLZ help.
Code: Select all
#include <iostream>
#include<string.h>
#include <algorithm>
using namespace std;
int main ()
{
long i,j,k,l,n;
char myints[1000],s[1001];
scanf("%ld",&n);
while(n--)
{
long a[130]={0};
scanf("%s",&myints);
k=strlen(myints);
for(i=0;i<k;i++)
{
a[myints[i]]++;
}
l=0;
for(j=65;j<=90;j++)
{
if(a[j])
{
for(i=0;i<a[j];i++)
s[l++]=j;
}
if(a[j+32])
{
for(i=0;i<a[j+32];i++)
s[l++]=j+32;
}
}
s[l]='\0';
do
{
printf("%s\n",s);
} while ( next_permutation (s,s+l) );
}
return 0;
}
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 195: anagram, wrong answer
next permutation function wont be able to solve it. STL is too slow. again suppose the string is aaaaaaaaaaaaaaa. thats 15 characters,but ans is only one line, "aaaaaaaaaaaaaaa". If you use STL and hashtable to eliminate the duplicates it will stil genarate 15! outputs and you will get TLE. only clever backtracking can solve the problem.
UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 195: anagram, wrong answer
Try this input..Mehadi wrote:What's problem in my Code .PLZ help
Code: Select all
1
Ba
My output is..
Code: Select all
aB
Ba
Re: 195: anagram, wrong answer
I totally disagree with you. I just solved this using STL's next_permutation(0.044s). It works fine if the string is aaaaaaaaaaaaaaaaaaaaaaaaaaaaa or aaaaaaaaaaaaaabaaaaaaaaaaaaaa etc.by Shafaet_du » Fri Oct 01, 2010 10:37 pm
next permutation function wont be able to solve it. STL is too slow. again suppose the string is aaaaaaaaaaaaaaa. thats 15 characters,but ans is only one line, "aaaaaaaaaaaaaaa". If you use STL and hashtable to eliminate the duplicates it will stil genarate 15! outputs and you will get TLE. only clever backtracking can solve the problem.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson
195 - WA Anagram I am stumped !!
My code works fine on my system. I have tested it with several inputs..
But i got WA .
Please help !!!
But i got WA .
Please help !!!
Code: Select all
Code deleted after AC
Last edited by mathgirl on Wed Apr 25, 2012 4:15 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 195 - WA Anagram I am stumped !!
On my system this code doesn't work. You shouldn't try to modify the data in a string.
http://www.cplusplus.com/reference/string/string/data/
Instead of pushing word onto your list you can create a new string from letters.
http://www.cplusplus.com/reference/string/string/data/
Instead of pushing word onto your list you can create a new string from letters.
Check input and AC output for thousands of problems on uDebug!
Re: 195 - WA Anagram I am stumped !!
I got the problem.. it was in the sorting order. I wrote a custom compare function for sort and got accepted.
Modifying the original string should work fine on any system. next_permutation is an STL algorithm, so it cant be wrong.
Modifying the original string should work fine on any system. next_permutation is an STL algorithm, so it cant be wrong.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 195 - WA Anagram I am stumped !!
The problem wasn't in next_permutation, the sort function didn't work because you had:
char *letters=(char*)word.data();
sort(letters,letters+len);
Here letters is a pointer to an internal location which should not be modified directly in the program. Its contents are guaranteed to remain unchanged only until the next call to a non-constant member function of the string object.
Instead you could have done:
char letters[len+1];
strcpy(letters,word.c_str());
sort(letters,letters+len);
And instead of pushing back word onto your list, do:
string s(letters);
output.push_back(s);
char *letters=(char*)word.data();
sort(letters,letters+len);
Here letters is a pointer to an internal location which should not be modified directly in the program. Its contents are guaranteed to remain unchanged only until the next call to a non-constant member function of the string object.
Instead you could have done:
char letters[len+1];
strcpy(letters,word.c_str());
sort(letters,letters+len);
And instead of pushing back word onto your list, do:
string s(letters);
output.push_back(s);
Check input and AC output for thousands of problems on uDebug!
Re: 195 - WA Anagram I am stumped !!
Thank brian ! I'll make sure to follow this next time.
195 - Anagram
Whats wrong with my code...plzz help
Code: Select all
Code removed after AC
Last edited by @ce on Mon Jun 25, 2012 10:01 am, edited 2 times in total.
-@ce
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 195 - Anagram
Input:
AC output:
Code: Select all
1
aAbB
Code: Select all
AaBb
AabB
ABab
ABba
AbaB
AbBa
aABb
aAbB
aBAb
aBbA
abAB
abBA
BAab
BAba
BaAb
BabA
BbAa
BbaA
bAaB
bABa
baAB
baBA
bBAa
bBaA
Check input and AC output for thousands of problems on uDebug!