CareerCup

I think binary search should be the choice. First, change and sort the dictionary in the order of characters (example apple -> aelpp -> sort those transitions). Then binary sort to find the closest relation to the word, do it backward from the destination to the starting

my idea:
build a "relation graph" for the dictionary first, in which a node is a word in the dictionary, an edge refers to a "one character different" relationship between two nodes.

after this pre-processing is done, when looking up for shortest path, just do BFS from the starting word...

Since it allows to change one character at a time,the length of execution depends number of character in the word.

Mostly we need to make relation graph by changing the characters.

Read this
http://en.wikipedia.org/wiki/Edit_distance

for this question, do you need to code for it or just provide the algorithm for it?

i think one must go for smaller work to higher work...
greedy approach... may not be successful always.
like we have
PAN -> MET
first possibility if would search it in dictionary
PAN > MAN
PAN > PEN
PAN > PAT
if PEN found
then
PEN > MEN
PEN > PET

lets suppose PET met in the dictionary then
PET > MET

ya you can ask that it might be possible if none of such word happens to be there at some point in time, then.
correct then i will say try regular expression by putting wild cards...
like
PAN > MAN
PAN > PEN
PAN > PAT
if none of the above found
then i would find a word such that
PAN > ?AN >?EN
PAN > ?AN >?AT
PAN > P?N >M?N
PAN > P?N >P?T
PAN > PA? >MA?
PAN > PA? >PE?

And similarly my search will keep on going until i find something.
Well it may still not be the confirm approach. but it will take minimum time on average

Turn the word set into a graph. Create edges between two words that have one different letter. Then, when a query arrives, use the A* shortest path algorithm to go from the starting word to the goal word. Each edge will have a weight of one. This is considered one of the most efficient path-finding algorithms in AI, and should get the job done.

Check out http://en.wikipedia.org/wiki/A-star_algorithm

If several queries are expected and we have the opportunity to cache, use the all pairs shortest path on a matrix approach (though this would result in 1,000,000 elements due to a 1000x1000 array).

#include<iostream>
using namespace std;
bool wordTrans(char* src,char *dest,char *result, bool *index,int length)
{
	bool changed=false;
	for(int i=0;i<length;i++)
	{
		if(src[i]!=dest[i] && index[i]==false)
		{
			index[i]=true;
			result[i]=dest[i];
			changed=true;
			break;
		}
	}
	return changed;
}
bool isWord(char* word,int length)
{
	//thresher implementation
	return true;
}

void wordTransition(char* src,char *dest,int length)
{
	char* result=(char*)malloc(sizeof(char)*length);
	bool* index=(bool*)malloc(sizeof(bool)*length);
	for(int i=0;i<length;i++)
	{
		result[i]=src[i];
		index[i]=0;
	}
	do
	{
		if(isWord(result,3))
			cout<<result<<endl;

	}while(wordTrans(src,dest,result,index,length));
	return;
}
int main()
{
	wordTransition("PAN","MET",3);
	return 0;
}

dude did you test this code?

here's the summary of my approach
say dictionary has nf words, and our 2 words have m chars
1. collect words in a list from dictionary that have just m chars. Let this list have say n words. - O(nf) time and space
2. for each word in the list, the number of words you can transform in by changing one character only is 24m. Make a list of these 24m words. Find the intersection of these 24m words with the list of valid m-char words we have. These are the words that the word under consideration can transform into. Let us call this set S1 Time - O(n) or O(m lgm) whichever is greater. O(n) i guess
3. Do the same for all the remaining m-char words. O(n^2). So we have n sets - S1,S2... Sn
4. Now that we have all possible transformations in m char words possible we have to contruct a graph of how these words transform into each other. In fact S1, S2 etc.. give us the adjaceny list representation already. No.of vertices = n. No. of edges should be less than n^2.
5. Now do BFS from initial word - PAN and when we hit MET its depth is the answer. Complexity shud be O(n^2) but not sure of this...

algo -

> we see the words as a node in a relation graph .
> one char change gives us a new node only when by changing one char we get a dictionary word . (here dictionary is a HASH table O(1) look up ).
> we need only BFS as the nodes differ by one char (or one unit distance ).

> BFS takes O(V+E).......n letters in initial word so a max of (26)^n words . so for a n letter word this is an exponential algorithm :-)

A*.
heuristic : edit distance