public int minDistance(String word1, String word2) {

        int m = word1.length();
        int n = word2.length();

        int[][] distances = new int[m + 1][n + 1];
        //insert
        for (int i = 0; i <= m; i++) {
            distances[i][0] = i;
        }
        //delete
        for (int i = 0; i <= n; i++) {
            distances[0][i] = i;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //if match, no change, no step
                if (word1.charAt(i) == word2.charAt(j)) {
                    distances[i + 1][j + 1] = distances[i][j];
                } else {
                    //current position, replace
                    int replace = 1 + distances[i][j];
                    
                    int insert = 1 + distances[i + 1][j];
                    int delete = 1 + distances[i][j + 1];
                    distances[i + 1][j + 1] = Math.min((Math.min(replace, insert)), delete);
                }
            }
        }
        return distances[m][n];
    }