字符串的距离(动态规划) - leetcode 72

最近我发的N篇文章都会是动态规划相关的题目

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

来看题

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"

输出: 3

解释:

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"

输出: 5

解释:

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u')

对于这道题,首先比较难很快的定义出一个状态,状态转换方程也比较绕。

从一个单词s1到单词s2,需要多少步操作能够达到呢?

比如从空字符串""到字符串"hello",需要多少步呢?显然需要5步,因为一直加字符就好了。

那么从字符串"hello"到空字符串"",需要多少步呢?也只需要5步,因为一直减就好了。

我们定义状态dp(i,j)为:字符串s1(0,i)变成字符串s2(0,j)所需要的步数。

那么必有状态转移方程

dp(i,j) = min(插入,删除,替换,相等)

假设s1(0,i) 是字符串str1c,s2(0,j)是字符串str2d

删除:dp(i, j) = dp(i-1, j) + 1 (删除c,则有str1与str2d)

插入:dp(i, j) = dp(i, j-1) + 1(在c后面添加d,str1cd与str2d,双方都去掉d,则有str1c与str2)

替换:dp(i, j) = dp(i-1, j-1) + 1

相等:dp(i, j) = dp(i-1, j-1)

状态转移方程不是简单的数学函数,而是一个组合函数,多个条件之间选择最小值。复杂的动态规划往往是这样。

最后整理一下写代码。

源代码:gcc

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define printf //printf

int min(int x, int y)
{
    return x > y ? y : x;
}

/*
dp(i, j) 定义:字符串s1 0到i 与 字符串s2 0到j 之间的距离
也就是:s1(0, i) s2(0, j)之间的距离
*/

int minDistance(char* word1, char* word2) {
    int l1 = strlen(word1);
    int l2 = strlen(word2);

    if (l1 == 0 && l2 == 0) {
        return 0;
    }

    //初始化
    int dp[l1+1][l2+1];
    for(int i=0; i<=l1; ++i){
        for(int j=0; j<=l2; ++j){
            dp[i][j] = 0;
        }
    }

    //一直删除,需要l1步
    for(int i=0; i<= l1; ++i){
        dp[i][0] = i;
        printf("%d %d -> %d\n", i, 0, dp[i][0]);
    }

    //一直增加,需要l2步
    for(int j=0; j<=l2; ++j){
        dp[0][j] = j;
        printf("%d %d -> %d\n", 0, j, dp[0][j]);
    }

    //自底向上
    for(int i=1; i<= l1; ++i){
        for(int j=1; j<= l2; ++j){
            //置换
            int replace = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;
            //插入: dp[i][j] = dp[i][j-1] + 1 因为s[0,j]与s[0,j-1]相隔一个字符
            //删除: dp[i][j] = dp[i-1][j] + 1 因为s[0, i]与s[0, i-1]相隔一个字符
            int ins_del = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
            dp[i][j] = min(replace, ins_del);

            printf("%d %d -> %d\n", i, j, dp[i][j]);
        }
    }

    return dp[l1][l2];
}

int main()
{
    printf("%d\n", minDistance("ab", "a"));
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-06-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蜉蝣禅修之道

算法考试填数字问题

2022
来自专栏分布式系统和大数据处理

正则表达式教程

1075
来自专栏机器学习之旅

tf.scan 记录

tf.scan(fn, elems, initializer=None, parallel_iterations=10, back_prop=True, swa...

1272
来自专栏个人分享

二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该...

1092
来自专栏chenjx85的技术专栏

leetcode-46-全排列

vector<vector<int>> permute(vector<int>& nums) 

2473
来自专栏前端儿

ASCII码排序

输入第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据,每组输入数据都是占一行,有三个字符组成,之间无空格。输出对于每组输入数据,输出一行,字符中间...

1872
来自专栏数据结构与算法

23:二维数组回形遍历

23:二维数组回形遍历 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个row行col列的整数数组array,要求从array[0][0...

5086
来自专栏数据结构与算法

3038 3n+1问题

3038 3n+1问题  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver 题解 题目描述 Description 3n+...

3657
来自专栏我的博客

C编程笔记

1.编译命令gcc test.c -o test 带上参数o就是指定编译文件名 2.printf(“%.2lf”,b) 其中前面2是小数点后位数,l是字母...

3695
来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

611

扫码关注云+社区

领取腾讯云代金券