Edit Distance LeetCode solution in Java

1
class Solution {
2

3
  public int minDistance(String word1, String word2) {
4
    int m = word1.length();
5
    int n = word2.length();
6
    int dp[][] = new int[m][n];
7
    for (int i = 0; i < m; i++) {
8
      for (int j = 0; j < n; j++) {
9
        dp[i][j] = -1;
10
      }
11
    }
12
    return solve(word1, word2, m - 1, n - 1, dp);
13
  }
14

15
  public int solve(String str1, String str2, int m, int n, int dp[][]) {
16
    if (m < 0) {
17
      return n + 1;
18
    }
19
    if (n < 0) {
20
      return m + 1;
21
    }
22
    if (dp[m][n] != -1) {
23
      return dp[m][n];
24
    }
25
    if (str1.charAt(m) == str2.charAt(n)) {
26
      return solve(str1, str2, m - 1, n - 1, dp);
27
    } else {
28
      int min = Math.min(solve(str1, str2, m - 1, n, dp), solve(str1, str2, m, n - 1, dp));
29
      dp[m][n] = 1 + Math.min(min, solve(str1, str2, m - 1, n - 1, dp));
30
    }
31
    return dp[m][n];
32
  }
33
}