Path reconstructions for SCS

[Sung-Pil_Paek]

class SCS {

  public int findSCSLength(String s1, String s2) {
    if (s1 == null || s2 == null) {
      throw new IllegalArgumentException();
    } else if (s1.length() == 0) {
      return s2.length();
    } else if (s2.length() == 0) {
      return s1.length();
    }

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

    for (int i = 1; i <= N1; i++) dp[i][0] = i;
    for (int i = 1; i <= N2; i++) dp[0][i] = i;

    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] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }

    java.util.List<Character> path = new java.util.LinkedList<>();
    int row = N1, col = N2;
    while (row > 0 || col > 0) {
      if (row == 0) path.add(0, s2.charAt(--col));
      else if (col == 0) path.add(0, s1.charAt(--row));
      else if (dp[row][col] != dp[row - 1][col]) path.add(0, s1.charAt(--row));
      else if (dp[row][col] != dp[row][col - 1]) path.add(0, s2.charAt(--col));
      else {
        path.add(0, s1.charAt(--row));
        col--;
      }
    }

    System.out.println(path);

    return dp[N1][N2];
  }

  public static void main(String[] args) {
    SCS scs = new SCS();
    System.out.println(scs.findSCSLength("abcf", "bdcf"));
    System.out.println(scs.findSCSLength("dynamic", "programming"));
  }
}