Did you mean..?解法

153 阅读 0 评论 101 点赞

我是靠谱客的博主可靠马里奥，这篇文章主要介绍Did you mean..?解法，现在分享给大家，希望可以做个参考。

题目如下：

这道题给了一个字典，和一个字符串，让你从字典中找到和已知字符串最相近的字符串并返回这个字符串。（下文中将已知字符串即为字符串to，字典中要比较的字符串记为dic）

解题思路：前半部分使用了编辑距离算法，计算edit_distance,然后构建一个map，将dic和它对应的edit_distance保存起来，将xiangsidu单独再存储在一个float数组中，利用Arrays.sort()方法排序，找到相似程度最大的值，在根据这个value在map中找到对应的key，这个key就是匹配程度最高的字符串。

编辑距离算法的动态规划公式

if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0

代码如下：