donnemartin / donnemartin/interactive-coding-challenges
Longest Common Subsequence algorithm wrong?
- 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
Assessment
This issue has not been assessed yet.