1146. Edit Step Ladders

单点时限: 3.0 sec

内存限制: 256 MB

An edit step is a transformation from one word to another word such that and are words in the dictionary, and can be transformed to by adding, deleting, or changing one letter. So the transformation from dig to dog or from dog to do are both edit steps. An edit step ladder is a lexicographically ordered sequence of words such that the transformation from to is an edit step for all from to .

输入格式

For a given dictionary, you are to compute the length of the longest edit step ladder.

The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds letters and there are no more than words in the dictionary.

输出格式

The output consists of a single integer, the number of words in the longest edit step ladder.

样例

Input
cat
dig
dog
fig
fin
fine
fog
log
wine
Output
5

5 人解决,9 人已尝试。

10 份提交通过,共有 29 份提交。

7.6 EMB 奖励。

创建: 12 年,10 月前.

修改: 2 年,4 月前.

最后提交: 8 年,1 月前.

来源: Waterloo local 2000.09.23

题目标签