题解 | #牛群编号变更#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param word1 string字符串
     * @param word2 string字符串
     * @return int整型
     */
    public static String string = "";
    public int minDistance (String word1, String word2) {
        // write code here
        search(0, word1, word2, new StringBuffer());
        int length = string.length();
        int length1 = word1.length() - length;
        int length2 = word2.length() - length;
        return length1 + length2;

    }

    public static void search(int index, String s1, String s2,
                              StringBuffer stringBuffer) {
        if (index == s1.length()) {
            return;
        }
        stringBuffer.append(s1.charAt(index));
        if (stringBuffer.length() > string.length() &&
                s2.contains(stringBuffer.toString())) {
            string = stringBuffer.toString();
        }
        search(index + 1, s1, s2, stringBuffer);
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        search(index + 1, s1, s2, stringBuffer);
    }
}

本题我并不是使用动态规划，而是使用递归方法，所用编程语言是java。

我们首先需要观察s1中随机抽取任意字符的最大数目是多少，且满足是s2的子序列，然后剩下的就是删除不是子序列的字符，插入s2中除了子序列的字符