public int minDistance(String s1, String s2) {

return minDistanceHelperDP(s1, s2, s1.length(), s2.length());

}

private int minDistanceHelperDP(String s1, String s2, int m, int n) {

int[][] dp = new int[m+1][n+1];

for (int i=0;i<=m;i++) {

for (int j=0;j<=n;j++) {

// First substring is empty

if (i == 0) {

dp[i][j] = j;

}

// Second substring is empty

else if (j == 0) {

dp[i][j] = i;

}

// If character are same, value is same as the previous dp array

else if (s1.charAt(i-1) == s2.charAt(j-1)) {

dp[i][j] = dp[i-1][j-1];

}

// If different, then 1 + min

else {

dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]));

}

}

}

return dp[m][n];

}