dp系列之编辑距离

数据结构动态规划
dp系列, 数据结构, 高频面试题总结

编辑距离

题目详情

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例：
给出 work1=”mart” 和 work2=”karma”
返回 3

思路：

  • 动态规划求解
  • dp[i][j]: word1的前i个字符转换成word2的前j个字符所需要的最少操作次数
  • 其中，状态转移方程为：dp[i][j] = Math.min {dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] (+1)}

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        // write your code here
        if (word1 == null || word2 == null)
            return 0;
        
        char[] chas1 = word1.toCharArray();
        char[] chas2 = word2.toCharArray();
        int row = chas1.length + 1;
        int col = chas2.length + 1;
        int[][] dp = new int[row][col];
        dp[0][0] = 0;
        for (int i = 1; i < row; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (chas1[i-1] == chas2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = dp[i-1][j-1] + 1; 
                    
                dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);  
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);  
            }
          
        }
        
        return dp[row-1][col-1];
        
    }
}

编辑距离ii

题目详情

给你两个字符串 S 和 T, 判断他们是否只差一步编辑。

样例：
给你字符串 s = “aDb”, t= “adb”
返回 true

思路：

只有以下三种可能性的时候才为只差一步编辑距离：

  • abcd <–> abce
  • abc <–> abcd
  • abce <–> abc

Ps：当两个字符串相等时，应该返回false

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    /**
     * @param s: a string
     * @param t: a string
     * @return: true if they are both one edit distance apart or false
     */
    public boolean isOneEditDistance(String s, String t) {
        // write your code here
        if (s.equals(t))
            return false;
            
        for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.length() == t.length())
                    return s.substring(i+1).equals(t.substring(i+1));
                else if (s.length() > t.length())
                    return s.substring(i+1).equals(t.substring(i));
                else if (s.length() < t.length())
                    return t.substring(i+1).equals(s.substring(i));
            }
        }
        
        return Math.abs(s.length() - t.length()) <= 1;
    }
}
Compartir Comentarios