My Accepted Java Solution
Hi: \n\nThis is a very interesting question and I found a [youtube video][1] that helps a lot.\nBasically the idea is to build up the solution step by step and 
Hi: \n\nThis is a very interesting question and I found a [youtube video][1] that helps a lot.\nBasically the idea is to build up the solution step by step and keep track of the previous optimal solution in a 2D array. In this 2D array dp, dp[i][j] means the operation needed to transform word1(0, i) to word2(0,j). \n\nThere can be three conditions:\n\n1, word1[i] == word2[j] : then no operation needed. dp[i][j] == dp[i-1][j-1]\n\n2, Do one operation on word1[i-1][j]. dp[i][j] = dp[i-1][j] + 1\n\n3, Do one operation on word2[i][j-1]. dp[i][j] = dp[i][j-1] + 1\n\nfor 2 and 3, the reason it works is that we know the optimal ways to transfrom word1(0,i) to word2(0,j-1) and word1(0,i-1) to word(0,j) ( Delete ("abc" to "ab") or Insert ("ab" to "abc") ). Now all we need to one more operation.\n\nThe code will be:\n\n    public int minDistance(String word1, String word2) {\n        if (word1.equals(word2)) {\n            return 0;\n        }\n        if (word1.length() == 0 || word2.length() == 0) {\n            return Math.abs(word1.length() - word2.length());\n        }\n        int[][] dp = new int[word1.length() + 1][word2.length() + 1];\n        for (int i = 0; i <= word1.length(); i++) {\n            dp[i][0] = i;\n        }\n        for (int i = 0; i <= word2.length(); i++) {\n            dp[0][i] = i;\n        }\n        for (int i = 1; i <= word1.length(); i++) {\n            for (int j = 1; j <= word2.length(); j++) {\n                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {\n                    dp[i][j] = dp[i - 1][j - 1];\n                } else {\n                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;\n                }\n            }\n        }\n        return dp[word1.length()][word2.length()];\n    }\n\n Remeber that we start from dp[0][0], which is an empty string to an empty string. \n\n\n  [1]: https://www.youtube.com/watch?v=z_CB7Gih_Mg
[]