Longest Common Subsequence algorithm wrong?

[ghost]

Longest Common Subsequence algorithm solution doesn't work on.

Here is the test case from Tushar Roy's video on Longest Common Subsequence (https://www.youtube.com/watch?v=NnD96abizww).

class TestLongestCommonSubseq(object):
    def test_another(self):
        str_comp = StringCompare()
        str0 = 'ABCDAF'
        str1 = 'ACBCF'
        expected = 'ABCF'
        assert_equal(str_comp.longest_common_subseq(str0, str1), expected)

The solution says

     13                 if i == 0 or j == 0:
     14                     T[i][j] = 0
---> 15                 elif str0[j - 1] != str1[i - 1]:
     16                     T[i][j] = max(T[i][j - 1],
     17                                   T[i - 1][j])

IndexError: string index out of range

[WyattJia]

Can you put you full file?

[havanagrawal]

Notebooks

• Challenge Notebook
• Solution Notebook

Bug The variables num_rows and num_cols are defined as:

num_rows = len(str0) + 1
num_cols = len(str1) + 1

i and j iterate over num_rows and num_cols respectively, but the offending line checks str0[j - 1] and str1[i - 1], i.e. i and j are swapped.

The bug will manifest itself in cases where len(str0) != len(str1)