about anagram

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

about anagram

Post by asif_rahman0 » Sat May 27, 2006 6:17 pm

can someone tell me how can i solve the anagram(454) problem?

plz help me to get this one.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon May 29, 2006 11:20 pm

Hi!

In "Programming Pearls" Bentley considers this problem - in case you want the algo.
In case you're in need of implementation details -I got RTE :(

Good luck!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

454 : Cant understand why WA WA WA WA

Post by tanvir_cse » Sat Nov 22, 2008 8:26 pm

I think my input - output format is incorrect. Can someone check this ? Whats wrong wtih my code.Got WA about 30 times !!!

#include<stdio.h>
#include<ctype.h>
#include<string.h>


int MAX_LINES;
char *lineptr[1000];
char str[100][100] , sorted[100][100],mas[100][100];

/*int readlines(char *lptr[], int maxlines);
void writelines(char *lptr[], int nlines);
void qsort(char *lptr[], int left, int right);
void sort_start(void) ;
*/

int isempty(char *a)
{
int t;
for(t=0;t<(int)strlen(a);t++)
if(!isspace(a[t]))
return 0;
return 1;
}

int main(void)
{
char s[100],ch,c,sort[100],temp,cdd;
int n,i,j,k,len,t,total,m,p;

scanf("%d",&n);
//scanf("%c",&cdd);
while( n-- )
{
printf("\n");
j=t=0;
for(i = 0; gets(s); ++i)
{
if(isempty(s))
break;
strcpy(str[j] , s);
j++;

}
total=j;
MAX_LINES=j;
//sort_start();

for(k=0; k<total; k++)
{
len=0;
for(m=0; str[k][m]; m++)
{
if(str[k][m]==' ')
continue;
else
sort[len++]=str[k][m];
}
sort[len]='\0';
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(sort>sort[j])
{
temp=sort;
sort=sort[j];
sort[j]=temp;
}

}
}
strcpy(sorted[t++],sort);
}

p=0;
for(i=0; i<total; i++)
{
for(j=i+1; j<total; j++)
{
if( (strcmp(sorted , sorted[j]))==0)
{
if( strcmp(str , str[j]) == -1)
{
strcat(mas[p],str);
strcat(mas[p] , " = ");
strcat(mas[p] , str[j]);
p++;
//sprintf(mas[p++],"%s = %s",str , str[j]);
}
else
{
strcat(mas[p],str[j]);
strcat(mas[p] , " = ");
strcat(mas[p] , str);
p++;
//sprintf(mas[p++],"%s = %s",str[j] , str);
}
}

}
}
//sort_start();
for(i=0; i<p; i++)
{
for(j=i+1; j<p; j++)
{
if( (strcmp(mas,mas[j])) ==0 )
{
strcpy(mas[i],"1");
}
}
}


for(i=0; i<p; i++)
{
if( (strcmp(mas[i],"1")) ==0 )
continue;
else
printf("%s\n",mas[i]);
}



if(n > 0) /*<--important*/
printf("\n");

}


}




/*
void sort_start(void)
{
int nlines;
if ((nlines = readlines(lineptr, MAX_LINES)) >= 0) {
qsort(lineptr, 0, nlines-1);
writelines(lineptr, nlines);
}

}


int readlines(char *lptr[], int maxlines)
{
int n;
for (n = 0; n < maxlines; n++)
{
lptr[n] = mas[n];
}
return n;
}


void writelines(char *lptr[], int nlines) {
for (int i= 0; i < nlines; i++)
{
// printf("%s\n", lptr[i]); // <stdio.h>
strcpy(mas[i] , lptr[i]);
//printf("%s\n", sorted[i]);
}

}

void qsort(char *v[], int left, int right) {
int i, last;
void swap(char **pa, char **pb);

if (left >= right) // do nothing if array contains
return ; // fewer than two elements.

for (last = left, i = left+1; i <= right; i++)
if (strcmp(v[i], v[left]) < 0) // <string.h>
swap(&v[++last], &v[i]);

swap(&v[left], &v[last]);
qsort(v, left, last-1);
qsort(v, last+1, right);
}
void swap(char **pa, char **pb) { // pointer to pointer
char *temp;
temp = *pa;
*pa = *pb;
*pb = temp;
}
*/

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: about anagram

Post by tryit1 » Sat Nov 22, 2008 11:20 pm



for(i=0;i<n;i++)
for(j=i+1,j<n;j++)
if( IsAnagrampair(s,s[j]))
print s = s[j]



int IsAnagrampair(string a,string b){
sort(a.begin(),a.end());
sort(b.begin(),b.end());
p= find the first index in a != <space>
q= find the first index in b != <space>
if( a.substr(p) == b.substr(q)) return 1;
return 0;
}

Post Reply

Return to “Algorithms”