题解 | #牛群编号变更#

知识点：动态规划

这是一个经典的动态规划题目，这道题目的关键是要找到两个字符串中的最长相同子字符串长度，定义dp[i][j]为word1到达i位置，word2到达j位置时，二者相同的子字符串长度值，此时dp[i][j]有两种情况，若i位置与j位置字符相同，则dp[i][j] = dp[i-1][j-1] + 1，表示子字符串长度加一，若两个位置的字符不同，则最长的长度有可能是去掉i字符时的最长长度，也有可能是去掉j字符时的最长长度，即max( dp[i-1][j], dp[i][j-1] )，遍历两个字符串，即可得到整个过程中出现的最长相同子字符串长度，答案即为两个字符串长度与两倍的子字符串长度之差。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    public int minDistance (String word1, String word2) {
        // write code here
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(word1.charAt(i) == word2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
                max = Math.max(dp[i + 1][j + 1], max);
            }
        }
        return m + n - 2 * max;
    }
}