LCS: remove the uncommon elements from the sequences

Revision ru1, by 0x81, 2023-05-12 01:57:43

The code (Ruby) below is a solution for https://leetcode.com/problems/uncrossed-lines/

Note: In Ruby Array#shift is O(1)

The trick is on the lines 14-15:

def max_uncrossed_lines a, b
    s = 0
    while !a.empty? && a.first == b.first
        a.shift
        b.shift
        s += 1
    end
    while !a.empty? && a.last == b.last
        a.pop
        b.pop
        s += 1
    end
    # These two lines
    c = a.to_set & b.to_set
    a, b = *[a, b].map! { | v | v.filter { c === _1 } }
    r0, r1 = *Array.new(2) { [0] * (b.size + 1) }
    for x in a
        for y, j in b.each_with_index
            r1[j + 1] = (x == y) ?
                1 + r0[j] :
                [r0[j + 1], r1[j]].max
        end
        r0, r1 = r1, r0
    end
    s + r0.last
end
Tags lcs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 0x81 2023-05-12 07:14:44 224
en1 English 0x81 2023-05-12 02:27:15 859 Initial revision for English translation
ru1 Russian 0x81 2023-05-12 01:57:43 859 Первая редакция (опубликовано)