class Solution { public int minDistance(String word1, String word2) { int m = word1.length() , n = word2.length(); return solve(word1 , word2 , m , n ,new Integer[m+1][n+1] ); /* every cell stores minimum cost needed to convert string till that row to string till that coloumn */ int dp[][] = new int [m+1][n+1]; //base case filling first row and coloumn for(int j = 0 ; j < dp[0].length ; j++) dp[0][j] = j; for(int i = 0 ; i < dp.length ; i++) dp[i][0] = i; for(int i = 1 ; i < dp.length ; i++){ for(int j = 1 ; j < dp[0].length ;j++){ if(word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else{ //replace int replace = dp[i-1][j-1]; //delete int delete = dp[i-1][j]; //insert int insert = dp[i][j-1]; //find min and add 1 for your own operation dp[i][j] = Math.min(replace ,Math.min(delete , insert)) +1; } } } return dp[m][n]; } //Recursion->3^m * 3^n Memo -> m*n | Sc- m*n + m+n(stack height) public int solve(String w1 , String w2 , int i , int j , Integer[][]dp ){ if(j == 0 ) //if i remains , you have to delete i characters to make w1 return i; if(i == 0) //if j remains , you have to inser j characters to make w2 return j; if(dp[i][j] != null) return dp[i][j]; //1 based indexing to handle base case better when turned to tabulization char ch1 = w1.charAt(i-1) , ch2 = w2.charAt(j-1); if(ch1 == ch2) return dp[i][j] = 0 + solve(w1 , w2 , i-1 , j-1 , dp); else{ int insert = solve(w1 ,w2 , i,j-1,dp); int delete = solve(w1 , w2 , i-1 , j , dp); int replace = solve(w1 , w2 , i-1 , j-1 , dp); return dp[i][j] = 1 + Math.min(insert , Math.min(delete , replace)); } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter