题型:问答题 标签:如何求字符串的编辑距离
题目:
编辑距离又称Levenshtein距离,是指两个字符串之间由一个转成另一个所需的最少编辑操作次 数。许可的编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。请设计并 实现一个算法来计算两个字符串的编辑距离,并计算其复杂度。在某些应用场景下,替换操作的代 价比较高,假设替换操作的代价是插入和删除的两倍,算法该如何调整?