From last time¶

Picking up from part 1, we have the following two examples:

In [1]:
A = 'ABCBDAB'
B = 'BDCABA'


There are two longest common subsequences:

1. B, C, B, A

2. B, D, A, B

In [2]:
occidental = "occidental"
superdelicately = "superdelicately"


One longest common subsequence (LCS) is: "deal".

Some code from part 1:

In [3]:
from functools import lru_cache

In [4]:
def pretty_print(arr):
'''A hacky function that makes every string in an array equal length, then prints
it row by row.'''
longest_length = len(arr[:-1][:-1])
nicer = []
for i, row in enumerate(arr):
new_row = []
for j, cell in enumerate(row):
cell_length = len(cell)
new_cell = cell + (' ' * padding_needed)
new_row.append(new_cell)
nicer.append(new_row)

[print(r) for r in nicer]

In [5]:
def lcs4(A, B, print_table=False):
# Create a lookup table. This is a 2D array with the letters of A as columns
# and the letters of B as rows. It includes a buffer row and column filled with empty strings.
columns = len(A) + 1
rows = len(B) + 1
lookup = [['' for n in range(columns)] for n in range(rows)]

# Since the lookup table is initialized with ''
# the base case (len(A) == 0 or len(B) == 0) is "baked-in".

# What's left is to go row by row, column by column and
# apply the iterative version of the recursive cases in lcs().
for row_id in range(1, rows):
for column_id in range(1, columns):
letter_in_A = A[column_id-1]
letter_in_B = B[row_id-1]
if letter_in_A == letter_in_B:
# "Recursive case 1"
lookup[row_id][column_id] = lookup[row_id - 1][column_id - 1] + letter_in_A
else:
# "Recursive case 2"
option1 = lookup[row_id][column_id-1]
option2 = lookup[row_id-1][column_id]
if len(option1) > len(option2):
lookup[row_id][column_id] = option1
else:
lookup[row_id][column_id] = option2

if print_table:
pretty_print(lookup)

return lookup[rows-1][columns-1]


A connection between LCS and LIS?¶

There is an interesting connection between longest common subsequence (LCS) and longest increasing subsequence (LIS).

The longest increasing subsequence of a list of numbers is equal to the longest common subsequence of that list of numbers and its sorted counterpart.

Source: "Course15.pdf" by Jean-Lou De Carufel (probably taken from Dasgupta et. al.).

In [6]:
nums = [3, 2, 1, 4]
nums

Out[6]:
[3, 2, 1, 4]
In [7]:
# Copy and sort nums
sorted_nums = nums[:]
sorted_nums.sort()
sorted_nums

Out[7]:
[1, 2, 3, 4]
In [8]:
# Convert both to strings
nums_str = [str(n) for n in nums]
sorted_nums_str = [str(n) for n in sorted_nums]

In [9]:
# Find the longest common subsequence of S and S_sorted.
lcs4(nums_str, sorted_nums_str)

Out[9]:
'14'

[1, 4] is a longest increasing subsequence of nums.

That said, this doesn't seem to work for lists with duplicate elements.

In [10]:
dupe_nums = [2, 2]

In [11]:
dupe_nums_str = ''.join([str(n) for n in dupe_nums])
dupe_nums_str

Out[11]:
'22'
In [12]:
lcs4(dupe_nums_str, dupe_nums_str)

Out[12]:
'22'

Whether $2 \rightarrow 2$ is "increasing" depends on how you define it. It is not strictly increasing and will fail to pass certain tests in this leetcode question.

Extending LCS to numbers¶

Thinking about it, my current implementation of longest common subsequence only works with lists of numbers where no number is greater than 9 (only single digits). With stringified number lists, there is no way to tell "10" from "1", "0".

The solution is simple: use lists instead of strings.

In [13]:
def lcs5(A, B):
# Create a lookup table. This is a 2D array with the letters of A as columns
# and the letters of B as rows. It includes a buffer row and column filled with empty strings.
columns = len(A) + 1
rows = len(B) + 1
lookup = [[[] for n in range(columns)] for n in range(rows)]

# Since the lookup table is initialized with ''
# the base case (len(A) == 0 or len(B) == 0) is "baked-in".

# What's left is to go row by row, column by column and
# apply the iterative version of the recursive cases in lcs().
for row_id in range(1, rows):
for column_id in range(1, columns):
letter_in_A = A[column_id-1]
letter_in_B = B[row_id-1]
if letter_in_A == letter_in_B:
# "Recursive case 1"
lookup[row_id][column_id] = lookup[row_id - 1][column_id - 1] + [letter_in_A]
else:
# "Recursive case 2"
option1 = lookup[row_id][column_id-1]
option2 = lookup[row_id-1][column_id]
if len(option1) > len(option2):
lookup[row_id][column_id] = option1
else:
lookup[row_id][column_id] = option2

return lookup[rows-1][columns-1]

In [14]:
numbers_a = ['10', '22', '5', '11', '10']
numbers_b = ['100', '22', '3', '11', '14']

In [15]:
lcs5(numbers_a, numbers_b)

Out[15]:
['22', '11']

Of course, letters still work:

In [16]:
occidental_letters = list(occidental)
occidental_letters

Out[16]:
['o', 'c', 'c', 'i', 'd', 'e', 'n', 't', 'a', 'l']
In [17]:
superdelicate_letters = list(superdelicately)
superdelicate_letters

Out[17]:
['s', 'u', 'p', 'e', 'r', 'd', 'e', 'l', 'i', 'c', 'a', 't', 'e', 'l', 'y']
In [18]:
lcs5(occidental_letters, superdelicate_letters)

Out[18]:
['d', 'e', 'a', 'l']

This combined with some input processing was enough to solve this HackerRank question.