All problems
Longest Common Subsequence of Tokens
Problem
Return the longest common subsequence of two token lists as a list of tokens.
When the reconstruction has a choice, advance in the first list on ties, which makes the result deterministic.
Hint
Build the DP table from the end, then walk forward following equal tokens first.
Test cases
case 1
in: [["a","b","c"],["a","c"]]
expected: ["a","c"]
case 2
in: [["the","cat","sat"],["the","dog","sat"]]
expected: ["the","sat"]
case 3
in: [[],["a"]]
expected: []
case 4
in: [["a","b"],["b","a"]]
expected: ["b"]
case 5
in: [["x","y","z","w"],["y","z","x"]]
expected: ["y","z"]
Starter codePython
def lcs_tokens(a, b):
# Your code here
pass5 test cases · run your code against them in the editor