LintCode 119. Edit Distance 原创Java参考解答

LintCode 119. Edit Distance 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/edit-distance/

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Example

Given word1 = "mart" and word2 = "karma", return 3.

解题思路

题目是求从word1变成word2的最小步骤数。

动态规划的代表题之一。动态规划方程f[i][j]表示从word1第i位置到word2第j位置的最小步骤数。

  • 初始化,word1第i位置到word2第0位置需要i步骤(删除i次)。
  • 初始化,word1第0位置到word2第j位置需要j步骤(插入j次)。
  • 其他位置上,f[i][j]是word1第i – 1位置到word2第j位置 + 1(添加1次),word1第i位置到word2第j – 1位置 + 1(删除1次),word1第i – 1位置到word2第j – 1位置的最小值(word1第i – 1位置和word2第j – 1位置相等则就是f[i – 1][j – 1],不相等则f[i – 1][j – 1] + 1(替换字母))。

参考代码

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注