[LeetCode]72 Edit Distance

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));
    }
}