P3488.第3题-命令行参数提示

2000ms

Difficulty: 5

所属公司 : 华为

算法与标签>动态规划

题目内容

在使用命令行工具时，经常会出现手工输入错字母的情况，如想要输入：

git clone

输入成了

git clane

因此为了命令行工具更易用，需要从支持的子命令列表中找到最相似的子命令提示给用户。最相似的定义为最短莱文斯坦距离：即两个字符串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括：

$1.$ 将一个字符替换成另一个字符

$2.$ 插入一个字符

$3.$ 删除一个字符

输入描述

第一行给出可提示的最短距离 $D$ ，第二行给出子命令数量 $N$ ，后面 $N$ 行给出所有的子命令列表，最后一行给出用户输入的子命令。

约束：

$1≤D≤5$
$1≤N≤30000$
单个子命令长度，子命令只包含小写字母

输出描述

输出为分三种情况：

$1.$ 用户输入的子命令正确匹配上某个子命令参数，输出原命令。

$2.$ 用户输入的子命令没有匹配上某个子命令参数，但是符合提示要求，则输出提示命令，如 $clone$ ；如果符合提示要求的子命令有多个，则按距离从小到大排序后输出，同一个距离内还有多个的按字母序从小到大输出。

$3.$ 用户输入的子命令没有匹配上某个子命令参数，且没有符合提示要求的子命令，则输出 $None$

样例1

输入

2
5
aprint
bprint
aaprint
bbprint
output
print

输出

aprint bprint aaprint bbprint

说明

子命令中有四个满足与 $print$ 的距离小于等于 $2$ ，其中 $aprint$ 与 $bprint$ 与目标的距离为 $1$ ，先将其排序并输出， $aaprint\ bbprint$ 与目标距离为 $2$ ，排序后接在前面输出后继续输出

样例2

输入

2
3
clone
checkout
switch
create

输出

None

说明

输入的三个子命令中没有满足与 $creat$ 距离小于等于 $2$ 的，因此输出 $None$

样例3

输入

2
3
clone
checkout
switch
clane

输出

clone

说明

第一行值为 $2$ ，表示当前输入不能完全正确匹配某个子命令时，则将其最短距离小于 $2$ 的子命令作为提示输出；第二行为 $3$ ，表示命令行实际有 $3$ 个子命令，分别为后续 $3$ 行；最后一行为用户实际的输入。由于用户没有命中具体的子命令，而 $clone$ 与用户输入的距离为 $1$ ，满足小于 $2$ 的要求，因此输出 $clone$

输入

预期输出（选填）

解题思路与方法

算法概述

详细方法

P3488.第3题-命令行参数提示

题目内容

输入描述

输出描述

样例1

样例2

样例3

Status

Development

Support

About