编程介的小学生 2019-12-27 21:31 采纳率: 20.5%
浏览 68

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 matlab图像高斯低通滤波
    • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
    • ¥15 钢筋实图交点识别,机器视觉代码
    • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
    • ¥50 400g qsfp 光模块iphy方案
    • ¥15 两块ADC0804用proteus仿真时,出现异常
    • ¥15 关于风控系统,如何去选择
    • ¥15 这款软件是什么?需要能满足我的需求
    • ¥15 SpringSecurityOauth2登陆前后request不一致
    • ¥15 禅道二次开发编辑版本,上传不了发行包