字符串编辑距离

题目描述:给定一个源串和目标串，能够对源串进行如下操作：在给定位置上插入一个字符替换任意字符删除任意字符写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。关于字符串最短编辑距离的解题思路:给定相关数据的定义:mep[i][j]表示源字符串source[0..i]到目标字符串target[0...j]的编辑距离,为了能够使用动态规划来解决相关的问题,首先要写出相关状态转移方程.在写出方程之前,对上面的题目进行分析:假设给定两个字符串source:ALGORITHM,target:ALTRUISTIC,先对两个字符串进行对其操作:A L G O R   I   T H MA L T   R U I S T I Csource[i]与target[j]的对应情况主要分为下面四种情况:字符--字符,字符--空白,空白--字符,空白--空白首先分析第一种情况:字符--字符:    当source[i]==target[j]时,mep[i][j]=mep[i-1][j-1];    当source[i]!=target[j]时,mep[i][j]=mep[i-1][j-1]+1;字符--空白:    考虑子字符串,也就是说也就说mep[i-1][j]是存在的,因为目标串在该位置处为空白,说明j不会发生变化,    但是源字符串只有i-1才匹配(状态转移);所以mep[i][j]=mep[i-1][j]+1;空白--字符    同理mep[i][j] = mep[i][j-1]+1;空白--空白 忽略综上所述总的状态转移方程为:    mep[i][j]=min(mep[i][j-1]+1,mep[i-1][j]+1,(source[i]==target[j]?0:1))题目二:传统的编辑距离里面有三种操作，即增、删、改，我们现在要讨论的编辑距离只允许两种操作，即增加一个字符、删除一个字符。我们求两个字符串的这种编辑距离，即把一个字符串变成另外一个字符串的最少操作次数。假定每个字符串长度不超过1000，只有大写英文字母组成。根据题目所述:两个字符串进行对其操作A L G O R   I   T H MA L   T R U I S T   I C以上三中情况不会出现:字符--字符情况,把这中情况省略即可
public class MinEditDistance {    static int minEditDistance(String source, String target) {        int SLen = source.length();        int TLen = target.length();        int mep[][] = new int[SLen][TLen];        for (int i = 0; i < SLen; i++) {            mep[i][0] = i;        }        for (int j = 0; j < TLen; j++) {            mep[0][j] = j;        }        for (int i = 1; i < SLen; i++) {            for (int j = 1; j < TLen; j++) {                if (source.charAt(i) == target.charAt(j)) {                    mep[i][j] = mep[i - 1][j - 1];                } else {                    //mep[i][j] = min(mep[i - 1][j] + 1, mep[i][j - 1] + 1);没有"改"操作时的算法                    mep[i][j] = min(mep[i-1][j-1]+1,min(mep[i - 1][j] + 1, mep[i][j - 1] + 1));                }            }        }        return mep[SLen - 1][TLen - 1];    }    static int min(int a, int b) {        return a > b ? b : a;    }    public static void main(String[] args) {//        String str = "ALGORITHM";//        String str1 = "ALTRUISTIC";        String str = "math";        String str1 = "mouth";        System.out.PRintln(minEditDistance(str, str1));    }}