Path reconstructions for subsequence

[Sung-Pil_Paek]

class LCS {

  public int findLCSLength(String s1, String s2) {
    int N1 = s1.length(), N2 = s2.length();
    int[][] dp = new int[N1 + 1][N2 + 1];

    int max = 0;
    for (int i = 1; i <= N1; i++) {
      for (int j = 1; j <= N2; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          dp[i][j] = 1 + dp[i - 1][j - 1];
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
        max = Math.max(max, dp[i][j]);
      }
    }

    java.util.List<Character> path = new java.util.LinkedList<>();

    int col = N2;
    int row = N1;

    while (col > 0 && row > 0) {
      if (dp[row][col] == dp[row - 1][col]) row--;
      else if (dp[row][col] == dp[row][col - 1]) col--;
      else {
        path.add(0, s1.charAt(row - 1));
        row--;
        col--;
      }
    }

    System.out.println(path);

    return max;
  }
  
  public static void main(String[] args) {
    LCS lcs = new LCS();
    System.out.println(lcs.findLCSLength("abdca", "cbda"));
    System.out.println(lcs.findLCSLength("passport", "ppsspt"));
  }
}

A slight tweak would work for palindromic subsequence as well :]