动态规划经典题目-字符串的编辑距离

25-03-07 18:21

3490

9767

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-atom-one-dark">

class="toc">

文章目录

一、题目描述
二、解题思路
三、代码实现
四、执行结果
五、拓展

一、题目描述

编辑距离(edit distance)— 我们把两个字符串的相似度定义为:将一个字符串转换成另外一个字符串时需要付出的代价。转换可以采用插入、删除和替换三种编辑方式，因此转换的代价就是对字符串的编辑次数。而编辑距离就是从一个字符串到另一个字符串的最少编辑次数。

示例：

以字符串“SNOWY”和“SUNNY”为例，下面是两种将“SNOWY”转换为“SUNNY”的方法

转换方法1：

S - N O W Y
S U N N - Y
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

转换代价Cost = 3 (插入U、替换O、删除W)

转换方法2：

- S N O W - Y
S U N - - N Y
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

转换代价Cost = 5 (插入S、替换S、删除O、删除W、插入N)。

不同的转换方法需要的编辑次数也不一样，最少的那个编辑次数就是字符串的编辑距离。

二、解题思路

设字符串P为模式串，T为文本串。在模式串P进行编辑成为T。

1. 定义状态

设dp[i][j]为P₁,P₂,…,P_i和结束于j的T的某个前缀片段之间文本差异的最小值。换言之，dp[i][j]是一下三种能给出较短字符串方式所花费用的最小值：

若P_i = T_j,则为dp[i-1][j-1]，反之则为dp[i-1][j-1] + 1。这意味着，要么第i个字符和第j个字符匹配，要么我们得用T_j替换P_j。这取决于这两个尾部字符是否相同。
dp[i][j-1]。意味着文本中多一个字符，因此我们需要前移文本串的位置指针，但得为模式串插入操作支付一次费用。
dp[i-1][j]。这意味着模式中多了一个字符，得删除它，因此我们需要前移模式串的位置指针，但得为删除操作支出一次费用。

2. 定义状态转移方程

当 P[i] = T[k]时，有

$d p [i] [j] = d p [i - 1] [j - 1]$

否则：

${\begin{cases} d p [i - 1] [j - 1] + 1 \\ d p [i - 1] [j] + 1 \\ d p [i] [j - 1] + 1 \end{cases}$

d p [i] [j] = m a x ⎩ ⎪ ⎨ ⎪ ⎧ d p [i - 1] [j - 1] + 1 d p [i - 1] [j] + 1 d p [i] [j - 1] + 1

3. 初始化

dp[0][j] 初始化为j。

dp[i][0] 初始化为i。

三、代码实现

/**
 * 字符串最小编辑距离
 *
 * @author hh
 */
public class MinEditDistance {

    /**
     * 求字符串p和字符串t的最小编辑距离
     *
     * @param p 模式串
     * @param t 文本串
     * @return 最小编辑距离
     */
    public int minDistance(String p,String t){
        int[][] dp = new int[p.length() + 1][t.length() +1];
        //初始化行
        for(int i = 0 ; i <= t.length(); i++ ){
            dp[0][i] = i;
        }
        //初始化列
        for(int i = 0; i <= p.length(); i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= p.length(); i++){
            for(int j = 1; j <= t.length(); j++){
                dp[i][j] = Integer.MAX_VALUE;
                if (p.charAt(i - 1) == t.charAt(j -1)) {
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]);
                }else{
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] + 1);
                }
                //和删除比较
                dp[i][j] = Math.min(dp[i][j],dp[i-1][j] + 1);
                //和插入比较
                dp[i][j] = Math.min(dp[i][j],dp[i][j-1] + 1);
            }
        }
        return dp[p.length()][t.length()];
    }

    public static void main(String[] args){
        String p = "steve";  // "thou-shalt-not";
        String t = "setve"; // "you-should-not";
        MinEditDistance minEditDistance = new MinEditDistance();
        System.out.println(minEditDistance.minDistance(p,t));
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

四、执行结果

五、拓展

我们在打字时经常会犯换位错误(交换了相邻的字符),例如你想录入“steve"却打成了“setve".在编辑距离的常规定义体系下，换位需要两次替换来修正.

请纳入一种交换操作,使得此类相邻字符间的换位错误只需一次操作即可.

状态方程定义如下：

当 P[i] = T[k]时，有

$dp[i-1][j-1],i-1\geq0,j-1\geq0$

当P[i] = T[j-1]且P[i-1]=T[j]时

$1,i-2\geq0,j-2\geq0$

否则：

${\begin{cases} d p [i - 1] [j - 1] + 1, & i - 1 \geq 0, j - 1 \geq 0 \\ d p [i - 1] [j] + 1, & i - 1 \geq 0 \\ d p [i] [j - 1] + 1, & j - 1 \geq 0 \end{cases}$

代码请读者自己实现。

注：本文转载自blog.csdn.net的仁者乐山智者乐水的文章"https://blog.csdn.net/qq_39559641/article/details/117192831"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

/ 登录

评论记录：

未查询到任何数据！