擅长:python、mysql、java
<p>这是一个非常简单的DP问题,您只需检查删除、编辑和插入:</p>
<pre class="lang-py prettyprint-override"><code>def getMinTotalNumChanges(str1, str2, memo=None):
if memo is None:
memo = {}
if str1 == "":
return len(str2)
if str2 == "":
return len(str1)
if (str1, str2) in memo:
return memo[(str1, str2)]
diff = 1 if str1[0] != str2[0] else 0
ret = min(
# deletion
1 + getMinTotalNumChanges(str1[1:], str2, memo),
# edit
diff + getMinTotalNumChanges(str1[1:], str2[1:], memo),
# insertion
1 + getMinTotalNumChanges(str1, str2[1:], memo)
)
memo[(str1, str2)] = ret
return ret
str1 = "password"
str2 = "pss$wr#d"
print(getMinTotalNumChanges(str1, str2))
</code></pre>