1. // User function Template for Java
  2. class Node
  3. {
  4.     int i;
  5.     int j;
  6.     String str;
  7.  
  8.     Node(int i, int j, String str)
  9.     {
  10.         this.i = i;
  11.         this.j = j;
  12.         this.str = str;
  13.     }
  14. }
  15.  
  16. class Solution {
  17.     // TreeSet automatically keeps elements sorted lexicographically.
  18.     Set<String> set = new TreeSet<>();
  19.  
  20.     /** Memoization **/
  21.     public List<String> allLCS(String s1, String s2) {
  22.         int n = s1.length();
  23.         int m = s2.length();
  24.  
  25.         // step-1 create a matrix
  26.         int[][] t = new int[n+1][m+1];
  27.  
  28.         // step-2 initialise the matrix acc. to base condition
  29.         for(int i=0; i<n+1; i++)
  30.         {
  31.             for(int j=0; j<m+1; j++)
  32.             {
  33.                 // Base case: If either string is empty, LCS is 0.
  34.                 if(i == 0 || j == 0)
  35.                     t[i][j] = 0;
  36.             }
  37.         }
  38.  
  39.         // step-3 convert recursive code to iterative
  40.         for(int i=1; i<n+1; i++)
  41.         {
  42.             for(int j=1; j<m+1; j++)
  43.             {
  44.                 // If the current characters match, add 1 to the previous LCS length.
  45.                 if(s1.charAt(i-1) == s2.charAt(j-1))
  46.                 {
  47.                     t[i][j] = 1 + t[i-1][j-1];
  48.                 }
  49.                 // If the current characters do not match, take the maximum of the LCS
  50.                 // when one character from either string is excluded.
  51.                 else
  52.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  53.             }
  54.         }
  55.  
  56.         // print all LCS
  57.         printAllLCS(s1, s2, n, m, t, "");
  58.         List<String> list = new ArrayList<>();
  59.         list.addAll(set);
  60.         return list;
  61.     }
  62.  
  63.     public void printAllLCS(String s1, String s2, int i, int j, int[][] t, String str)
  64.     {
  65.         if(i == 0 || j == 0)
  66.         {
  67.             set.add(new StringBuilder(str).reverse().toString());
  68.             return;
  69.         }
  70.  
  71.         if(s1.charAt(i-1) == s2.charAt(j-1))
  72.         {
  73.             printAllLCS(s1, s2, i-1, j-1, t, str + s1.charAt(i-1));
  74.         }
  75.         else
  76.         {
  77.             // If both equal → explore both paths (this creates multiple LCS).
  78.             if(t[i-1][j] >= t[i][j-1])
  79.                 printAllLCS(s1, s2, i-1, j, t, str);
  80.  
  81.             if(t[i][j-1] >= t[i-1][j])
  82.                 printAllLCS(s1, s2, i, j-1, t, str);
  83.         }
  84.     }
  85.  
  86.     /** Top-Down Approach **/
  87.     public List<String> allLCS(String s1, String s2) {
  88.         int n = s1.length();
  89.         int m = s2.length();
  90.  
  91.         // step-1 create a matrix
  92.         int[][] t = new int[n+1][m+1];
  93.  
  94.         // step-2 initialise the matrix acc. to base condition
  95.         for(int i=0; i<n+1; i++)
  96.         {
  97.             for(int j=0; j<m+1; j++)
  98.             {
  99.                 // Base case: If either string is empty, LCS is 0.
  100.                 if(i == 0 || j == 0)
  101.                     t[i][j] = 0;
  102.             }
  103.         }
  104.  
  105.         // step-3 convert recursive code to iterative
  106.         for(int i=1; i<n+1; i++)
  107.         {
  108.             for(int j=1; j<m+1; j++)
  109.             {
  110.                 // If the current characters match, add 1 to the previous LCS length.
  111.                 if(s1.charAt(i-1) == s2.charAt(j-1))
  112.                 {
  113.                     t[i][j] = 1 + t[i-1][j-1];
  114.                 }
  115.                 // If the current characters do not match, take the maximum of the LCS
  116.                 // when one character from either string is excluded.
  117.                 else
  118.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  119.             }
  120.         }
  121.  
  122.         Stack<Node> st = new Stack<>();
  123.         st.push(new Node(n, m, ""));
  124.  
  125.         while(!st.isEmpty())
  126.         {
  127.             Node curr = st.pop();
  128.             int i = curr.i;
  129.             int j = curr.j;
  130.             String s = curr.str;
  131.  
  132.             if(i == 0 || j == 0)
  133.             {
  134.                 set.add(new StringBuilder(s).reverse().toString());
  135.                 continue;
  136.             }
  137.  
  138.             if(s1.charAt(i-1) == s2.charAt(j-1))
  139.                 st.push(new Node(i-1, j-1, s + s1.charAt(i-1)));
  140.  
  141.             else
  142.             {
  143.                 // explore both paths
  144.                 if(t[i-1][j] >= t[i][j])
  145.                     st.push(new Node(i-1, j, s));
  146.  
  147.                 if(t[i][j-1] >= t[i][j])
  148.                     st.push(new Node(i, j-1, s));
  149.             }
  150.         }
  151.         List<String> list = new ArrayList<>();
  152.         list.addAll(set);
  153.         return list;
  154.     }
  155. }