使用递归列表的最长公共子序列

Question

我试图找到类型可比的两件事之间的最长公共子序列。我有算法，但我想通过递归方法调用将这些项目添加到列表中，但我不知道如何以这种方式将最后一项添加到列表中。

这里是我的代码：

public static <E extends Comparable<E>>List<E> getLongestCommonSubSeq(
    List<E> x, 
    List<E> y) 
{ 
    int m = x.size() +1; 
    int n = y.size() +1; 
    String[][] b =new String [m][n]; 
    int[][] c = new int[m][n]; 
    for(int i=1;i<m;i++) { 
     c[i][0] = 0; 
    } 
    for(int j = 0;j<n;j++) { 
     c[0][j]= 0; 
    } 
    for(int i=1; i<m;i++) { 
     for(int j=1;j<n;j++) { 
     if(x.get(i).equals(y.get(j))) { 
      c[i][j] = c[i-1][j-1]+1; 
      b[i][j]="NW"; 
     } 
     else if(c[i-1][j] >= c[i][j-1]) { 
      c[i][j]=c[i-1][j]; 
      b[i][j]="N"; 
     } 
     else { 
      c[i][j] = c[i][j-1]; 
      b[i][j]= "W"; 
     } 
     } 
    } 
    return getLCS(m,n, b, x); 
} 

public static <E extends Comparable<E>> List<E> getLCS(
    int  i, 
    int  j, 
    String[][] b, 
    List<E> x) 
{ 
    if(i==0 || j ==0) 
     return null; 
    if(b[i][j].equals("NW")) { 
     // This can't be done because add returns a boolean type 
     return getLCS(i-1,j-1, b, x) .add(x.get(i)); 
    } 
    if(b[i][j].equals("N")) { 
     return getLCS(i-1,j, b, x); 
    } 
    if(b[i][j].equals("W")) { 
     return getLCS(i, j-1, b, x); 
    } 
    return null; 
} 

Answer 1

public static <E extends Comparable<E>>List<E> getLCS(int i, int j, String[][] b, List<E> x){ 
     List<E> ret = new ArrayList<E>(); 


     if(i==0 || j ==0) 
      return ret; 

     if(b[i][j].equals("NW")) { 
      // This can't be done because add returns a boolean type 

      ret=getLCS(i-1,j-1, b, x); 
      ret.add(x.get(i)); 
     }else if(b[i][j].equals("N")) { 
      ret = getLCS(i-1,j, b, x); 
     }else if(b[i][j].equals("W")) { 
      ret= getLCS(i, j-1, b, x); 
     } 


     return ret; 
    } 

我实现它有点不对劲