CareerCup

are we given the another word?

Looks like TRIE data structure question.

@Anonymous

Dictionary can be quite big.

Minimum edit distance can solve the problem but in that we are actually given a word to which we need to make a match.
But here it is a dictionary in which it can match to any word.

Two concerns:
1)If we are going to add a word than which word need to be added.If we are looking for all possible characters than it sounds like very inefficient.
2)To what extent the word length can increase.This is still a question mark until we iterate dictionary to find actual length.

I was going through some spell checker algorithms in the web. Found this one very useful. May be this solves the basic concept to the problem.

norvig.com/spell-correct.html

I believe its about the levenshtein distance algorithm. Please refer the following link

Refer Wikipedia for more.

Thanks

Vinod Varma ( vinodbvarma@gmail.com)

Its about String alignment. for eg the strings:-

String A:> bat
String B:> bath
String C:> cat

we use Alignment scores:
if 2 different chars align, score = 2. It represents a replace(del nd insert op)
if a char match with a space, score = 1. It represents an insert op.

Now consider Alignment with A,C:-
b-a-t
c-a-t
here 'b' aligns with 'c' so score = 2.

Consider string A,B:-
b-a-t
b-a-t-h
here 'h' aligns with a space: ' '. so score = 1.
this score is min, so the nearest string is bath and it involves an insert operation.

This is a standard 'string alignment' problem. can google it.

But the question is how to get the other strings to which we should compare with ?
I am not getting any idea how to go 4 it...
guess compare it with all the strings in the dictionary, using 'branch and bound' technique, starting with the nearest strings as a heuristic.