10508 - Word Morphing

[shihabrc]

Hi all,

I've tried to solve this problem by:
1.computing the distance of the words frm the 1st word.
2. Sort(ascending) the words on the basis of the distances and output them all.

But, i'm getting OLE. I don't know why. Can someone help me with some suggetions. And is anything wrong in my approach.

Code: Select all

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

typedef struct Word{
	char word[1005];//edited after AC
	int d;
} Word;

Word word[1005];//edited after AC

int comp(const void* a, const void *b){
	Word* x=(Word*) a;
	Word* y=(Word*) b;

	return x->d - y->d;
}

void main(){
	int i,j,m,n;

//	freopen("C:\\4.txt","r",stdin);

	while(scanf("%d %d",&m,&n)==2){
		getchar();

		for(i=0;i<m;i++){
			word[i].d=0;
			gets(word[i].word);
			for(j=0;j<n;j++) if(word[0].word[j]!=word[i].word[j]) word[i].d++;
		}

		qsort(word,m,sizeof(Word),comp);

		for(i=0;i<m;i++) puts(word[i].word);
	}
}

-Shihab

[mamun]

Your approach is alright. Are you sure you're getting OLE?

[shihabrc]

Ya, I got OLE in the first 2 submissions. But, today when i made a 3rd submission (with the same code) I got WA. After changing some array size I finally got AC. But , it took too much memory. I saw that a lot of ppl hav solved it with very low memory spent. How can I optimize the space complexity. And, i think this prob can also be solved with BFS(this prob has very much similarity with prob 429). If i'm wrong correct me.

-Shihab

[yiuyuho]

heh, I am getting PE for this problem....I don;t see anything tricky about the formatting, you're just outputting the words (and I preserved all upper/lower cases).

Any ideas?

[yiuyuho]

I see that the above posted code gets AC, so I am guessing from 'a' to 'A' is considered a change as well?

I thought changing means changing the letter to a different alphabet....

[sujon]

Code: Select all

#include<iostream.h>
#include<stdio.h>
#include<string.h>
#define max 25000

	   // #include<conio.h>

int main()
{
			 //   clrscr();

char word[max][max],input[max];
char w[max],mor[max];

long int n,l,i,count,j;

//freopen("input.txt","r",stdin);
while(gets(input))
{

sscanf(input,"%ld %ld",&n,&l);

gets(w);
gets(mor);

for(j=0;j<n-2;j++)
{

gets(input);

   count=0;

 for(i=0;i<l;i++)
  if(input[i]!=w[i])
   count++;

 strcpy(word[count-1],input);
}


puts(w);

for(i=0;i<l-1;i++)
puts(word[i]);
puts(mor);

}

return 0;
}