LeetCode : 583. Delete Operation for Two Strings 最长公共子序列

谁践踏了优雅 2021-06-24 16:10 319阅读 0赞

**试题：**  
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:  
Input: “sea”, “eat”  
Output: 2  
Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”.  
Note:  
The length of given words won’t exceed 500.  
Characters in given words can only be lower-case letters.

**代码**  
dp\[i\]\[j\]记录串x1x2⋯xi与y1y2⋯yj的LCS长度  
初始化条件：在列为0或行为0时dp\[\]\[\]都为0  
[【动态规划】最长公共子序列与最长公共子串][Link 1]

class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length(), len2 = word2.length();
            int[][] dp = new int[len1+1][len2+1];
            for(int i=1; i<=len1; i++){
                for(int j=1; j<=len2; j++){
                    if(word1.charAt(i-1)==word2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }else{
                        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            return len1+len2-dp[len1][len2]*2;
        }
    }

[Link 1]: http://www.cnblogs.com/en-heng/p/3963803.html

发表评论取消回复

表情：

评论列表（有 0 条评论，319人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-1143. 最长公共子序列

目录题目思路动态规划题目来源 [1143. 最长公共子序列][1143.] 题目思路 LeetCode-718. 最长重复子

「爱情、让人受尽委屈。」/ 2024年03月26日 22:03/ 0 赞/ 56 阅读

相关 leetcode300-最长公共子序列

文章目录嘴上上升子序列题目描述 code 方法一: 暴力求解法方式二

系统管理员/ 2023年05月30日 04:56/ 0 赞/ 1 阅读

相关 leetcode1143最长公共子序列

最长公共子序列例 "abc" "abc" count=3 思想：dp[n][m]，动态规划 dp[i][j]是str1[

逃离我推掉我的手/ 2023年03月13日 12:25/ 0 赞/ 2 阅读

相关 LeetCode1143. 最长公共子序列

难度：中等题目描述： > 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子

╰+哭是因爲堅強的太久メ/ 2022年10月22日 07:32/ 0 赞/ 142 阅读

相关 LeetCode 1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：

小咪咪/ 2022年10月22日 04:15/ 0 赞/ 150 阅读

相关 leetcode 583. Delete Operation for Two Strings | 583. 两个字符串的删除操作（最长公共子序列，DP）

题目 [https://leetcode.com/problems/delete-operation-for-two-strings/][https_leetcode.c

客官°小女子只卖身不卖艺/ 2022年08月28日 08:56/ 0 赞/ 165 阅读

相关最长公共子序列空间优化最长公共子序列

import java.util.Scanner; / HDU 1159 @author ashzheng 201

ゞ浴缸里的玫瑰/ 2022年08月21日 05:46/ 0 赞/ 266 阅读

相关 leetcode 583. Delete Operation for Two Strings 问题转换+最长公共子串 + DP动态规划

Given two words word1 and word2, find the minimum number of steps required to make word1

Myth丶恋晨/ 2022年06月03日 04:41/ 0 赞/ 134 阅读

相关【Leetcode】583.Delete Operation for Two Strings

Delete Operation for Two Strings Given two words word1 and word2, find the minimum nu

左手的ㄟ右手/ 2022年04月14日 21:16/ 0 赞/ 110 阅读

相关 LeetCode : 583. Delete Operation for Two Strings 最长公共子序列

试题： Given two words word1 and word2, find the minimum number of steps required to make

谁践踏了优雅/ 2021年06月24日 16:10/ 0 赞/ 320 阅读