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