编程介的小学生 2019-09-22 21:51 采纳率: 20.5%
浏览 133

编写程序来实现 Word Ladder

Problem Description
A word ladder is a sequence of words, in which two consecutive words differ by exactly one letter. An example of such a ladder (usually arranged vertically, hence the "ladder" would be: beer, brew, brow, word, down. Note that to get from one word to the next, the letters may be rearranged, and exactly one letter is changed.
For this problem, you will be given a dictionary of distinct words, all of the same length. Your task is to write a program that finds a word ladder of minimal length, such that the first and last word of the ladder have no letters in common.

Input
On the first line an integer t (1<=t <= 100): the number of test cases. Then for each test case:

A line with two space-separated integers n (2 <= n <= 100) and l (1 <= l <= 20): the number of words and their length.

n lines with a word, each consisting of l lowercase letters (a - z).

Output
For each testcase:

a single line with the words in a ladder of minimal length, separated by a single space.

It is guaranteed that at least one such ladder can be constructed. If there is more than one, output the one that comes first lexicographically.

Notes:
If s and t are strings of equal length and si denotes the ith character of s, then s precedes t lexicographically if for some i: si < ti and sj = tj for all j < i.

Sample Input
1
9 3
alt
spy
sea
opt
pea
ape
spa
apt
ale

Sample Output
ale alt apt opt

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
    • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
    • ¥15 Arcgis相交分析无法绘制一个或多个图形
    • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
    • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
    • ¥30 3天&7天&&15天&销量如何统计同一行
    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型