https://oj.leetcode.com/problems/edit-distance/
http://blog.csdn.net/linhuanmars/article/details/24213795
public class Solution {
public int minDistance(String word1, String word2)
{
if (word1 == null || word2 == null)
return -1;
if (word1.isEmpty())
return word2.length(); // Insert
if (word2.isEmpty())
return word1.length(); // Insert
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
// m[i][j] 表示 word1 的前i个字符和 word2 的前j个字符 的最少操作数是多少
int[][] m = new int[chars1.length][chars2.length];
// 对于word1的第一个字符 和 word2 的第一个字符
// 如果相同，无操作
// 不同，一个置换
m[0][0] = chars1[0] == chars2[0] ? 0 : 1;
for (int i = 1 ; i < chars1.length ; i ++)
{
// 对于word1 比对 word2的第一个字符
// 如果相同，只需要插入word1 i 之前的字符，为i
// 如果不同，
// 如果word1 之前字符都不同，1个置换+i个插入， 为i+1
// 如果之前有相同的，取上一个值+1个插入，为m[i-1][j] + 1
// 列类似
if (chars1[i] == chars2[0])
m[i][0] = i; // insert before
else
m[i][0] = Math.min(i, m[i - 1][0]) + 1;
}
for (int i = 1 ; i < chars2.length ; i ++)
{
if (chars1[0] == chars2[i])
m[0][i] = i;
else
m[0][i] = Math.min(i, m[0][i - 1]) + 1; // on more insert
}
for (int i = 1 ; i < chars1.length ; i ++)
{
for (int j = 1 ; j < chars2.length ; j ++)
{
if (chars1[i] == chars2[j])
{
// 如果字符相同，
m[i][j] = m[i - 1][j - 1];
}
else
{
// 如果不同
// 可以置换1个
// 或插入word1
// 或插入word2
m[i][j] = min(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1]) + 1;
}
}
}
return m[chars1.length - 1][chars2.length - 1];
}
private int min(int a, int b, int c)
{
return Math.min(a, Math.min(b, c));
}
}原文：http://7371901.blog.51cto.com/7361901/1598952