跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0498. Problem E: Edit Step Ladders

  • ID: 504
  • 传统题
  • 10000ms
  • 128MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • 高校与竞赛共享题
  • 英文题面
  • 题目来源
  • 题面语言

Problem E: Edit Step Ladders

题目描述

Problem E: Edit Step Ladders

An edit step is a transformation from one word x to another word y such that x and y are words in the dictionary, and x can be transformed to y 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 w1, w2, ... wn such that the transformation from wi to wi+1 is an edit step for all i from 1 to n-1.

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 16 letters and there are no more than 25000 words in the dictionary. The output consists of a single integer, the number of words in the longest edit step ladder.

样例 1

输入

cat
dig
dog
fig
fin
fine
fog
log
wine

输出

5

题目来源:fps-zhblue-waterloo-000923.xml;FPS 共享题包,题包内第 5 题。保留原作者与原赛事署名。