longestCommonSubsequence<T> function

List<T> longestCommonSubsequence<T>(List<T> a, List<T> b)

Compute the longest common subsequence of two lists.

Implementation

List<T> longestCommonSubsequence<T>(List<T> a, List<T> b) {
  final m = a.length;
  final n = b.length;
  // DP table
  final dp = List.generate(m + 1, (_) => List.filled(n + 1, 0));
  for (var i = 1; i <= m; i++) {
    for (var j = 1; j <= n; j++) {
      if (a[i - 1] == b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  // Backtrack
  final result = <T>[];
  var i = m, j = n;
  while (i > 0 && j > 0) {
    if (a[i - 1] == b[j - 1]) {
      result.add(a[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return result.reversed.toList();
}