-
Notifications
You must be signed in to change notification settings - Fork 0
/
common_child_test.py
85 lines (72 loc) · 2.31 KB
/
common_child_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# https://www.hackerrank.com/challenges/common-child/problem
# https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
import unittest
# TODO: improve performance; not passing tests on hackerrank
def commonChild(s1, s2):
m = len(s1)
n = len(s2)
arr = [[None for i in range(n + 1)] for j in range(m + 1)]
# recursive function to calculate longest common subsequence
def lcs(s1, s2, m, n):
# check if intermediate result already known
if arr[m][n] is not None:
return arr[m][n]
# base case
if n == 0 or m == 0:
result = 0
# case 1: last letters match
elif s1[m - 1] == s2[n - 1]:
result = 1 + lcs(s1, s2, m-1, n-1)
# case 2: last letters don't match
else:
temp1 = lcs(s1, s2, m, n-1)
temp2 = lcs(s1, s2, m-1, n)
if temp1 > temp2:
result = temp1
else:
result = temp2
arr[m][n] = result
return result
return lcs(s1, s2, m, n)
class MyTest(unittest.TestCase):
def test_1(self):
s1 = "HARRY"
s2 = "SALLY"
received = commonChild(s1, s2)
expected = 2
self.assertEqual(received, expected)
def test_2(self):
s1 = "SHINCHAN"
s2 = "NOHARAAA"
received = commonChild(s1, s2)
expected = 3
self.assertEqual(received, expected)
def test_3(self):
s1 = "AABCD"
s2 = "ABACD"
received = commonChild(s1, s2)
expected = 4
self.assertEqual(received, expected)
def test_4(self):
s1 = "ABACD"
s2 = "AABCD"
received = commonChild(s1, s2)
expected = 4
self.assertEqual(received, expected)
def test_5(self):
s1 = "OUDFRMYMAW"
s2 = "AWHYFCCMQX"
received = commonChild(s1, s2)
expected = 2
self.assertEqual(received, expected)
def test_6(self):
# we could miss a longer child if we latch on to a smaller child
# in the following example, ACDE is the longest child
# to find it, we'd have to skip over B in s1!
s1 = "ABCDE"
s2 = "ACDEB"
received = commonChild(s1, s2)
expected = 4
self.assertEqual(received, expected)
if __name__ == '__main__':
unittest.main()