题目描述
编辑距离也称莱文斯坦距离,指的是两个字符串之间,由一个转化为另一个所需的最少编辑操作次数,允许的编辑操作包括:
1. 将其中一个字符替换为另一个字符
2. 插入一个字符
3. 删除一个字符
例如,字符串 `"ab"` 可以通过修改一个字符变为 `"ac"`,可以通过增加一个字符变为 `"acb"`,也可以通过删除一个字符变为 `"a"`,所以 `"ab"` 与 `"ac", "acb", "a"` 的编辑距离都为 $1$。当然两个相等的字符串的编辑距离为 $0$。
现在,小 Z 有 $n$ 个英语单词,他用这些单词组成了一个英语词典,这样当他遇到一个单词时,就可以通过查词典的方式来帮助记忆。
具体地,小 Z 将 $n$ 个单词编辑成词典,然后接下来会遇到 $q$ 个需要查询的单词,对于每一个查询单词,如果词典中某一个单词和这个查询的单词的编辑距离 $\le 1$,那么就输出词典中的这个单词。如果不存在这样的单词,就输出 `No`。
「一些出题人善意的提示」
1. 数据保证答案唯一
2. 字符串 $s$ 与字符串 $t$ 的编辑距离 $\le 1$,有如下 $4$ 情况:
- $s$ 与 $t$ 相同;$s$ 可以通过删除一个字符变为 $t$;$s$ 可以通过增加一个字符变为 $t$;$s$ 可以通过修改一个字符变为 $t$。
输入
第一行输入两个整数 $n,q$ 分别表示词典中单词的个数和询问的单词个数。
接下来 $n$ 行,每行一个一个字符串表示词典中初始的单词。
接下来 $q$ 行,每行一个字符串表示小 Z 这次询问的单词。
输出
输出共 $q$ 行,对于每一次询问输出词典中与询问单词编辑距离 $\le 1$ 的单词。如果不存在,则输出 `No`。
5 5
input
output
example
cjiajia
dict
nput
inpuxt
input
dicti
ditc
input
input
input
dict
No
提示
对于 $60\%$ 的数据,满足词典中要么只有与询问完全相同的单词,要么答案为 `No`。
对于 $100\%$ 的数据,满足 $1\le n \le 50,1\le q\le 50$,单词长度 $\le 20$,单词仅由小写字母组成。数据保证每一组询问的答案唯一。