0

比較可能なタイプの2つのものの間で最長共通サブシーケンスを見つけようとしています。アルゴリズムがダウンしていますが、再帰メソッド呼び出しを介してこれらのアイテムをリストに追加したいのですが、この方法で最後のアイテムをリストに追加する方法がわかりません。

これが私のコードです：

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;
}
4

1 に答える 1

0 
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;
    }

私はそれを少し間違って実装していました

于 2013-02-13T02:26:45.973 に答える