Step by step explanation of how to optimize the solution from simple recursion to DP
First we may want to consider recursion.\n\npublic class Solution {\n    /**\n     * Recursive solution.\n     * For each poisition, check three subproblem:\n  
First we may want to consider recursion.\n```\npublic class Solution {\n    /**\n     * Recursive solution.\n     * For each poisition, check three subproblem:\n     * 1. insert\n     * 2. delete\n     * 3. replace\n     * We only modify the first string since no matter which one we choose, the result is the same. \n     * Got TLE since we recursively solve the same subproblem several times.\n     * Appromixately O(len1 ^ 3) time in the worst case.\n     * Need to optimize it using cache, which is the idea of dynamic programming. \n     * The key point is to find out the subproblem we have solved duplicately and cache the recursion.\n     * Noticed that each subproblem is specificed by i and j pointer, so we can cache the result of these subproblems. \n     */\n    public int minDistance(String word1, String word2) {\n        if (word1 == null || word1.length() == 0) return word2.length();\n        if (word2 == null || word2.length() == 0) return word1.length();\n        \n        return match(word1, word2, 0, 0);\n    }\n    \n    private int match(String s1, String s2, int i, int j) {\n        //If one of the string's pointer have reached the end of it\n        if (s1.length() == i) {\n            return s2.length() - j;\n        }\n        if (s2.length() == j) {\n            return s1.length() - i;\n        }\n        \n        int res;\n        //If current poisition is the same.\n        if (s1.charAt(i) == s2.charAt(j)) {\n            res = match(s1, s2, i + 1, j + 1);\n        } else {\n            //Case1: insert\n            int insert = match(s1, s2, i, j + 1);\n            //Case2: delete\n            int delete = match(s1, s2, i + 1, j);\n            //Case3: replace\n            int replace = match(s1, s2, i + 1, j + 1);\n            res = Math.min(Math.min(insert, delete), replace) + 1;\n        }\n        \n        return res;\n    }\n}  \n```\nThis got TLE. based on the analysis above, we may try DP. \n```\npublic class Solution {\n    /**\n     * Optimization using dynamic programming\n     * Top-down solution\n     * O(len1 * len2) time, O(len1 * len2) space\n     */\n    public int minDistance(String word1, String word2) {\n        if (word1 == null || word2 == null) return -1;\n        if (word1.length() == 0) return word2.length();\n        if (word2.length() == 0) return word1.length();\n        \n        char[] c1 = word1.toCharArray();\n        char[] c2 = word2.toCharArray();\n        \n        int[][] cache = new int[c1.length][c2.length];\n        for (int i = 0; i < c1.length; i++) {\n            for (int j = 0; j < c2.length; j++) {\n                cache[i][j] = -1;\n            }\n        }\n        \n        return match(c1, c2, 0, 0, cache);\n    }\n    \n    private int match(char[] c1, char[] c2, int i, int j, int[][] cache) {\n        if (c1.length == i) return c2.length - j;\n        if (c2.length == j) return c1.length - i;\n        \n        if (cache[i][j] != -1) {\n            return cache[i][j];\n        }\n        \n        if (c1[i] == c2[j]) {\n            cache[i][j] = match(c1, c2, i + 1, j + 1, cache);\n        } else {\n            //Case1: insert\n            int insert = match(c1, c2, i, j + 1, cache);\n            //Case2: delete\n            int delete = match(c1, c2, i + 1, j, cache);\n            //Case3: replace\n            int replace = match(c1, c2, i + 1, j + 1, cache);\n            \n            cache[i][j] = Math.min(Math.min(insert, delete), replace) + 1;\n        }\n        \n        return cache[i][j];\n    }\n    \n    \n    \n    \n    /**\n     * Bottom-up approach\n     */\n    public int minDistance(String word1, String word2) {\n        if (word1 == null || word2 == null) return -1;\n        if (word1.length() == 0) return word2.length();\n        if (word2.length() == 0) return word1.length();\n        \n        char[] c1 = word1.toCharArray();\n        char[] c2 = word2.toCharArray();\n        \n        int[][] matched = new int[c1.length + 1][c2.length + 1];\n        //matched[length of c1 already been matched][length of c2 already been matched]\n        \n        for (int i = 0; i <= c1.length; i++) {\n            matched[i][0] = i;\n        }\n        for (int j = 0; j <= c2.length; j++) {\n            matched[0][j] = j;\n        }\n        \n        for (int i = 0; i < c1.length; i++) {\n            for (int j = 0; j < c2.length; j++) {\n                if (c1[i] == c2[j]) {\n                    matched[i + 1][j + 1] = matched[i][j];\n                } else {\n                    matched[i + 1][j + 1] = Math.min(Math.min(matched[i][j + 1], matched[i + 1][j]), matched[i][j]) + 1;\n                    //Since it is bottom up, we are considering in the ascending order of indexes.\n                    //Insert means plus 1 to j, delete means plus 1 to i, replace means plus 1 to both i and j. \n                    //above sequence is delete, insert and replace. \n                }\n            }\n        }\n        \n        return matched[c1.length][c2.length];\n    }\n    \n}\n```
[]