#yyds干货盘点# 面试必刷TOP101:编辑距离(一)

时间:2022-10-08 10:01:23

1.简述:

描述

给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作:

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足 #yyds干货盘点# 面试必刷TOP101:编辑距离(一) ,保证字符串中只出现小写英文字母。

示例1

输入:

"nowcoder","new"

返回值:

6

说明:

"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次
"nowcoder"=>"new"(删除"coder"),删除操作5次
示例2

输入:

"intention","execution"

返回值:

5

说明:

一种方案为:
因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可
示例3

输入:

"now","nowcoder"

返回值:

5

2.代码实现:

import java.util.*;
public class Solution {
public int editDistance (String str1, String str2) {
int n1 = str1.length();
int n2 = str2.length();
//dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
int[][] dp = new int[n1 + 1][n2 + 1];
//初始化边界
for(int i = 1; i <= n1; i++)
dp[i][0] = dp[i - 1][0] + 1;
for(int i = 1; i <= n2; i++)
dp[0][i] = dp[0][i - 1] + 1;
//遍历第一个字符串的每个位置
for(int i = 1; i <= n1; i++)
//对应第二个字符串每个位置
for(int j = 1; j <= n2; j++){
//若是字符相同,此处不用编辑
if(str1.charAt(i - 1) == str2.charAt(j - 1))
//直接等于二者前一个的距离
dp[i][j] = dp[i - 1][j - 1];
else
//选取最小的距离加上此处编辑距离1
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
return dp[n1][n2];
}
}