donnemartin / donnemartin/interactive-coding-challenges

Longest Common Subsequence algorithm wrong?

Open
#225 2 comments 0 reactions 0 assignees View on GitHub
needs-review
Dominant language
Python
Stars
31.8k
Forks
4.7k
PR merge metrics
No merged PRs in 30d

Description

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
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.