def recursive_edit_distance(str1, str2, cost):
if not str1:
return len(str2) * cost["add"]
if not str2:
return len(str1) * cost["delete"]
if str1[-1] == str2[-1]:
return recursive_edit_distance(str1[:-1], str2[:-1], cost)
else:
return min(recursive_edit_distance(str1[:-1], str2, cost) + cost["delete"],
recursive_edit_distance(str1, str2[:-1], cost) + cost["add"],
recursive_edit_distance(str1[:-1], str2[:-1], cost) +
min(cost["replace"], cost["delete"] + cost["add"]))
def dp_edit_distance(str1, str2, cost):
value = [[0] * (len(str2) + 1) for i in range(len(str1) + 1)]
for i in range(len(str1) + 1):
value[i][0] = i * cost["delete"]
for j in range(len(str2) + 1):
value[0][j] = j * cost["add"]
for i in range(1, len(str1) + 1):
for j in range(1, len(str2) + 1):
if str1[i - 1] == str2[j - 1]:
value[i][j] = value[i - 1][j - 1]
else:
value[i][j] = min(value[i - 1][j] + cost["delete"],
value[i][j - 1] + cost["add"],
value[i - 1][j - 1] + min(cost["replace"], cost["delete"] + cost["add"]))
for i in range(len(value)):
print(value[i])
return value[-1][-1]
str_ = ["",
"a",
"abc",
"efa",
"bcc"]
cost = {"delete": 1, "add": 1, "replace": 1}
for i in range(len(str_)):
for j in range(i + 1, len(str_)):
print("str_[{}], str_[{}]:".format(i, j),
recursive_edit_distance(str_[i], str_[j], cost) == dp_edit_distance(str_[i], str_[j], cost))
str1 = "acef"
str2 = "abce"
print(dp_edit_distance(str1, str2, cost))
Processed:
0.009, SQL:
9
