求字符串的最小编辑距离动态规划（java实现）

妖狐艹你老母 2023-09-27 17:28 111阅读 0赞

**目录**

题目

算法思路

实现代码

--------------------

## **题目** ##

Levenshtein 距离，又称[编辑距离][Link 1]，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

**例如：**

字符串A: abcdefg

字符串B: abcdef

通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

**要求：**

给定任意两个字符串，写出一个算法计算它们的编辑距离。

数据范围：给定的字符串长度满足1<=len(str)<=1000

**输入描述：**

每组用例一共2行，为输入的2个字符串。

**输出描述：**

每组用例输出一行，代表字符串的距离。

**示例1**

输入：

abcdefg

abcdef

输出：1

--------------------

## 算法思路 ##

1、一个字符串的字符可以通过增加、删除和替换来变成另外一个一模一样的字符串，其中增加、删除和替换所需要的最小操作次数即为最小的编辑次数。

2、创建二维数组arr\[\]\[\] 来判断所需的最小编辑次数

定义 int\[ \]\[ \] arr = new int\[**s1.length()+1**\]\[**s2.length()+1**\],此处**数组多定义一行和一列是方便统计遍历字符串s1的第 i 位字符和字符串s2的第 j 位字符的编辑距离,数组最左上角元素为0可以忽略。**

3、初始化数组的第 0 行的各个元素值：空字符串转化为时s2字符串的编辑距离

>     //arr数组第一行：空字符串最少经过多少次变化可以变成字符串s2
>     for(int j= 1;j<=s2.length();j++){
>         arr[0][j]=j;
>     }

初始化数组的第 0 列的各个元素值：空字符串转化为s1字符串的编辑距离

>     //初始化arr数组第一列：空字符串最少经过多少次变化可以变成字符串s1
>      for(int i= 1;i<=s1.length();i++){
>          arr[i][0]=i;
>      }

4、比较字符串A的位置i处和字符串B的位置j处的两个元素是否相等：

1.  若相等，则 arr\[i\]\[j\]处元素值为**arr\[i - 1\]\[j - 1\]**；(当s1字符串的第i位字符与s2字符串的第j位字符相同时，此时的编辑距离仍为前面字符的编辑距离)
2.  若不等，则 arr\[i\]\[j\]处元素值为**Min(arr\[i - 1\]\[j - 1\]，arr\[i - 1\]\[j\]，arr\[i\]\[j - 1\]) + 1** （当s1字符串的第i位字符与s2字符串的第j位字符不相同时，此时的编辑距离为前面字符的最小编辑距离+1）

5、求s1字符串与s2字符串的最小编辑距离即返回**arr\[s1.length()\]\[s2.length()\]**

如下图所示举例说明：

s1:adfghy

s2:yuhg

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:115px;">编辑距离arr[i][j]</td> 
   <td style="width:72px;">null</td> 
   <td style="width:74px;">y</td> 
   <td style="width:76px;">u</td> 
   <td style="width:80px;">h</td> 
   <td style="width:81px;">g</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">null&nbsp; &nbsp; &nbsp;&nbsp;</td> 
   <td style="width:72px;">0</td> 
   <td style="width:74px;">1</td> 
   <td style="width:76px;">2</td> 
   <td style="width:80px;">3</td> 
   <td style="width:81px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">a&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;</td> 
   <td style="width:72px;">1</td> 
   <td style="width:74px;">1</td> 
   <td style="width:76px;">2</td> 
   <td style="width:80px;">3</td> 
   <td style="width:81px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">d&nbsp;</td> 
   <td style="width:72px;">2</td> 
   <td style="width:74px;">2</td> 
   <td style="width:76px;">2</td> 
   <td style="width:80px;">3</td> 
   <td style="width:81px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">f&nbsp;&nbsp;</td> 
   <td style="width:72px;">3</td> 
   <td style="width:74px;">3</td> 
   <td style="width:76px;">3</td> 
   <td style="width:80px;">3</td> 
   <td style="width:81px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">g&nbsp; &nbsp; &nbsp; &nbsp;</td> 
   <td style="width:72px;">4</td> 
   <td style="width:74px;">4</td> 
   <td style="width:76px;">4</td> 
   <td style="width:80px;">4</td> 
   <td style="width:81px;">3</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">h&nbsp; &nbsp; &nbsp;&nbsp;</td> 
   <td style="width:72px;">5</td> 
   <td style="width:74px;">5</td> 
   <td style="width:76px;">5</td> 
   <td style="width:80px;">4</td> 
   <td style="width:81px;">4</td> 
  </tr> 
  <tr> 
   <td style="width:115px;">y&nbsp; &nbsp; &nbsp; &nbsp;</td> 
   <td style="width:72px;">6</td> 
   <td style="width:74px;">5</td> 
   <td style="width:76px;">6</td> 
   <td style="width:80px;">5</td> 
   <td style="width:81px;">5</td> 
  </tr> 
 </tbody> 
</table>

--------------------

## 实现代码 ##

import java.util.HashSet;
    import java.util.Scanner;
    import java.util.Set;
    
    public class Main2 {
        public static void main(String[] args) {//计算字符串的编辑距离：一个字符串转换成另外一个字符串所需的最小编辑操作次数
            //许可编辑：替换、插入和删除
            Scanner scan = new Scanner(System.in);
            String s1 = scan.nextLine();
            String s2 = scan.nextLine();
            System.out.println(func(s1,s2));
    
        }
        public static int func(String s1,String s2){
            if(s1.equals(s2)){//当S1和S2相等时，编辑距离为0
                return 0;
            }
            //建立二维数组来存储s1字符串的每一位字符到s2字符串的每一位字符所需要编辑的距离
            //多建立一行和一列目的是方便统计遍历字符串的编辑距离，数组最左上角为0可以忽略
            int[][] arr = new int[s1.length()+1][s2.length()+1];
           //初始化arr数组第一列：空字符串最少经过多少次变化可以变成字符串s1
            for(int i= 1;i<=s1.length();i++){
                arr[i][0]=i;
            }
            //arr数组第一行：空字符串最少经过多少次变化可以变成字符串s2
            for(int j= 1;j<=s2.length();j++){
                arr[0][j]=j;
            }
    
            for(int i=1;i<=s1.length();i++){//从字符串s1第一位字符开始遍历
                for(int j=1;j<=s2.length();j++){//从字符串s2第一位字符开始遍历
                    if(s1.charAt(i-1) == s2.charAt(j-1)){//特别注意从字符串的第一个字符下标0开始比较
                        arr[i][j] = arr[i-1][j-1];//此时s1的第i位字符等于s2的第j位字符，此时编辑距离不变，仍为前面字符的编辑距离
                    }else{
                        //当s1的第i位字符不等于s2的第j位字符，此时编辑距离为前面字符最小的编辑距离+1
                        arr[i][j]=Math.min(arr[i-1][j-1],Math.min(arr[i][j-1],arr[i-1][j]))+1;
                    }
                }
            }
            return arr[s1.length()][s2.length()];
        }
    }

[Link 1]: https://so.csdn.net/so/search?q=%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB&spm=1001.2101.3001.7020