Saturday, June 12, 2010

Efficient dictionary

Given a dictionary of words D, find out the longest chain of 'ancestors' in it. Ancestors are defined in the following way: A word is said to be the parent of another word if (1) It is a valid word in D, (2) It can be obtained by deleting one character of the word and permuting the remaining characters.

What if we allow to delete k characters?

No comments:

Post a Comment