ROUGE-L LCS Length

Problem

Return the length of the longest common subsequence between token lists a and b using dynamic programming. This is the LCS term that ROUGE-L turns into precision, recall, and an F-score. Return 0 when either list is empty.

Hint

The subsequence need not be contiguous; reuse a rolling DP row.

Test cases

case 1

in: [["a","b","c"],["a","c"]]

expected: 2

case 2

in: [["a","b","c"],["d","e"]]

expected: 0

case 3

in: [[],[]]

expected: 0

case 4

in: [["x","y","z"],["x","y","z"]]

expected: 3

case 5

in: [["a","c","b"],["a","b","c"]]

expected: 2

Starter codePython

def rouge_l_lcs(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor