1. class Solution {
  2.     /**
  3.      * Find the LCS of both strings
  4.      * Once LCS length is found, we can remove the length of LCS from both the strings
  5.      * and then we can sum up the remaining length of both strings
  6.      */
  7.     public int minDistance(String word1, String word2) {
  8.         int n = word1.length();
  9.         int m = word2.length();
  10.  
  11.         int[][] t = new int[n+1][m+1];
  12.  
  13.         for(int i=0; i<n+1; i++)
  14.         {
  15.             for(int j=0; j<m+1; j++)
  16.             {
  17.                 if(i == 0 || j == 0)
  18.                     t[i][j] = 0;
  19.             }
  20.         }
  21.  
  22.         for(int i=1; i<n+1; i++)
  23.         {
  24.             for(int j=1; j<m+1; j++)
  25.             {
  26.                 if(word1.charAt(i-1) == word2.charAt(j-1))
  27.                 {
  28.                     t[i][j] = 1 + t[i-1][j-1];
  29.                 }
  30.                 else
  31.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  32.             }
  33.         }
  34.  
  35.         int lcsLength = t[n][m];
  36.  
  37.         return (n-lcsLength) + (m-lcsLength);
  38.     }
  39. }
  40.  
  41. // lcs: etco = 4
  42. // n = 8
  43. // m = 4