1. class Solution {
  2.     // idea: Find the LCS and then substract the length of LCS from sum of both strings length
  3.  
  4.     /** Recursion*/
  5.     public static int minSuperSeq(String s1, String s2) {
  6.  
  7.         int n = s1.length();
  8.         int m = s2.length();
  9.  
  10.         int length = findLCS(s1, s2, n, m);
  11.         return (n+m-length);
  12.     }
  13.  
  14.     public static int findLCS(String s1, String s2, int n, int m)
  15.     {
  16.         if(n == 0 || m == 0)
  17.             return 0;
  18.  
  19.         // choice diagram
  20.         if(s1.charAt(n-1) == s2.charAt(m-1))
  21.         {
  22.             return 1 + findLCS(s1, s2, n-1, m-1);
  23.         }
  24.  
  25.         else
  26.         {
  27.             int choice1 = findLCS(s1, s2, n-1, m);
  28.             int choice2 = findLCS(s1, s2, n, m-1);
  29.             return Math.max(choice1, choice2);
  30.         }
  31.     }
  32.  
  33.     /** Memoization*/
  34.     public static int minSuperSeq(String s1, String s2) {
  35.  
  36.         int n = s1.length();
  37.         int m = s2.length();
  38.  
  39.         int[][] t = new int[n+1][m+1];
  40.         for(int i=0; i<n+1; i++)
  41.             Arrays.fill(t[i], -1);
  42.  
  43.         int length = findLCS(s1, s2, n, m, t);
  44.         return (n+m-length);
  45.     }
  46.  
  47.     public static int findLCS(String s1, String s2, int n, int m, int[][] t)
  48.     {
  49.         if(n == 0 || m == 0)
  50.             return 0;
  51.  
  52.         if(t[n][m] != -1)
  53.             return t[n][m];
  54.  
  55.         // choice diagram
  56.         if(s1.charAt(n-1) == s2.charAt(m-1))
  57.         {
  58.             t[n][m] = 1 + findLCS(s1, s2, n-1, m-1, t);
  59.             return t[n][m];
  60.         }
  61.  
  62.         else
  63.         {
  64.             int choice1 = findLCS(s1, s2, n-1, m, t);
  65.             int choice2 = findLCS(s1, s2, n, m-1, t);
  66.             t[n][m] = Math.max(choice1, choice2);
  67.             return t[n][m];
  68.         }
  69.     }
  70.  
  71.     /** Top-down approach*/
  72.     public static int minSuperSeq(String s1, String s2) {
  73.  
  74.         int n = s1.length();
  75.         int m = s2.length();
  76.  
  77.         int[][] t = new int[n+1][m+1];
  78.  
  79.         // base condition
  80.         for(int i=0; i<n+1; i++)
  81.         {
  82.             for(int j=0; j<m+1; j++)
  83.             {
  84.                 if(i == 0 || j == 0)
  85.                     t[i][j] = 0;
  86.             }
  87.         }
  88.  
  89.         for(int i=1; i<n+1; i++)
  90.         {
  91.             for(int j=1; j<m+1; j++)
  92.             {
  93.                 if(s1.charAt(i-1) == s2.charAt(j-1))
  94.                 {
  95.                     t[i][j] = 1 + t[i-1][j-1];
  96.                 }
  97.                 else
  98.                     t[i][j] = Math.max( t[i-1][j], t[i][j-1] );
  99.             }
  100.         }
  101.  
  102.         int length = t[n][m];
  103.         return (n+m-length);
  104.     }
  105. }