Skip to content

Commit f438cd3

Browse files
JKLiang9714keon
JKLiang9714
authored and
keon
committed
fix bugs, add descriptions, and add tests (keon#486)
* fix: test_heap, tree/traversal/__init__ * fix a error in longest_non_repeat.py * fix bugs, add notes, and add tests
1 parent 3e6c93a commit f438cd3

6 files changed

Lines changed: 153 additions & 17 deletions

File tree

‎algorithms/arrays/longest_non_repeat.py‎

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@ def longest_non_repeat_v1(string):
1616
Find the length of the longest substring
1717
without repeating characters.
1818
"""
19+
if string is None:
20+
return 0
1921
dict = {}
2022
max_length = 0
2123
j = 0
@@ -52,18 +54,19 @@ def get_longest_non_repeat_v1(string):
5254
Return max_len and the substring as a tuple
5355
"""
5456
if string is None:
55-
return 0
57+
return 0, ''
5658
sub_string = ''
57-
temp = []
58-
max_len = 0
59-
for i in string:
60-
if i in temp:
61-
temp = []
62-
temp.append(i)
63-
if len(temp) > max_len:
64-
max_len = len(temp)
65-
sub_string = ''.join(temp)
66-
return max_len, sub_string
59+
dict = {}
60+
max_length = 0
61+
j = 0
62+
for i in range(len(string)):
63+
if string[i] in dict:
64+
j = max(dict[string[i]], j)
65+
dict[string[i]] = i + 1
66+
if i - j + 1 > max_length:
67+
max_length = i - j + 1
68+
sub_string = string[j: i + 1]
69+
return max_length, sub_string
6770

6871
def get_longest_non_repeat_v2(string):
6972
"""
@@ -73,7 +76,7 @@ def get_longest_non_repeat_v2(string):
7376
Return max_len and the substring as a tuple
7477
"""
7578
if string is None:
76-
return 0
79+
return 0, ''
7780
sub_string = ''
7881
start, max_len = 0, 0
7982
used_char = {}

‎algorithms/backtrack/anagram.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,12 @@
1+
"""
2+
Given two strings, determine if they are equal after reordering.
3+
4+
Examples:
5+
"apple", "pleap" -> True
6+
"apple", "cherry" -> False
7+
"""
8+
9+
110
def anagram(s1, s2):
211
c1 = [0] * 26
312
c2 = [0] * 26

‎algorithms/backtrack/generate_abbreviations.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
"""
22
given input word, return the list of abbreviations.
33
ex)
4-
word => [1ord, w1rd, wo1d, w2d, 3d, w3 ... etc]
4+
word => ['word', 'wor1', 'wo1d', 'wo2', 'w1rd', 'w1r1', 'w2d', 'w3', '1ord', '1or1', '1o1d', '1o2', '2rd', '2r1', '3d', '4']
55
"""
66

77

‎algorithms/backtrack/letter_combination.py‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,16 @@
22
Given a digit string, return all possible letter
33
combinations that the number could represent.
44
5+
A mapping of digit to letters (just like on the telephone buttons) is given below:
6+
2: "abc"
7+
3: "def"
8+
4: "ghi"
9+
5: "jkl"
10+
6: "mno"
11+
7: "pqrs"
12+
8: "tuv"
13+
9: "wxyz"
14+
515
Input:Digit string "23"
616
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
717
"""

‎tests/test_array.py‎

Lines changed: 36 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
flatten_iter, flatten,
44
garage,
55
josephus,
6-
longest_non_repeat_v1, longest_non_repeat_v2,
6+
longest_non_repeat_v1, longest_non_repeat_v2, get_longest_non_repeat_v1, get_longest_non_repeat_v2,
77
Interval, merge_intervals,
88
missing_ranges,
99
move_zeros,
@@ -169,6 +169,40 @@ def test_longest_non_repeat_v2(self):
169169

170170
string = "asjrgapa"
171171
self.assertEqual(longest_non_repeat_v2(string), 6)
172+
173+
def test_get_longest_non_repeat_v1(self):
174+
175+
string = "abcabcbb"
176+
self.assertEqual(get_longest_non_repeat_v1(string), (3, 'abc'))
177+
178+
string = "bbbbb"
179+
self.assertEqual(get_longest_non_repeat_v1(string), (1, 'b'))
180+
181+
string = "pwwkew"
182+
self.assertEqual(get_longest_non_repeat_v1(string), (3, 'wke'))
183+
184+
string = "dvdf"
185+
self.assertEqual(get_longest_non_repeat_v1(string), (3, 'vdf'))
186+
187+
string = "asjrgapa"
188+
self.assertEqual(get_longest_non_repeat_v1(string), (6, 'sjrgap'))
189+
190+
def test_get_longest_non_repeat_v2(self):
191+
192+
string = "abcabcbb"
193+
self.assertEqual(get_longest_non_repeat_v2(string), (3, 'abc'))
194+
195+
string = "bbbbb"
196+
self.assertEqual(get_longest_non_repeat_v2(string), (1, 'b'))
197+
198+
string = "pwwkew"
199+
self.assertEqual(get_longest_non_repeat_v2(string), (3, 'wke'))
200+
201+
string = "dvdf"
202+
self.assertEqual(get_longest_non_repeat_v2(string), (3, 'vdf'))
203+
204+
string = "asjrgapa"
205+
self.assertEqual(get_longest_non_repeat_v2(string), (6, 'sjrgap'))
172206

173207

174208
class TestMaxOnesIndex(unittest.TestCase):
@@ -314,7 +348,7 @@ def test_three_sum(self):
314348
{(-4, 1, 3), (-2, -1, 3), (-1, -1, 2)})
315349

316350

317-
class TestSuite(unittest.TestCase):
351+
class TestTwoSum(unittest.TestCase):
318352

319353
def test_two_sum(self):
320354

‎tests/test_backtrack.py‎

Lines changed: 82 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,12 +6,17 @@
66
array_sum_combinations,
77
unique_array_sum_combinations,
88
combination_sum,
9+
get_factors,
10+
recursive_get_factors,
911
find_words,
12+
generate_abbreviations,
13+
generate_parenthesis_v1,
14+
generate_parenthesis_v2,
15+
letter_combinations,
1016
pattern_match,
1117
)
1218

1319
import unittest
14-
from algorithms.backtrack.generate_parenthesis import *
1520

1621

1722
class TestAddOperator(unittest.TestCase):
@@ -110,6 +115,53 @@ def test_combination_sum(self):
110115
self.assertEqual(combination_sum(candidates2, target2), answer2)
111116

112117

118+
class TestFactorCombinations(unittest.TestCase):
119+
120+
def test_get_factors(self):
121+
target1 = 32
122+
answer1 = [
123+
[2, 16],
124+
[2, 2, 8],
125+
[2, 2, 2, 4],
126+
[2, 2, 2, 2, 2],
127+
[2, 4, 4],
128+
[4, 8]
129+
]
130+
self.assertEqual(sorted(get_factors(target1)), sorted(answer1))
131+
132+
target2 = 12
133+
answer2 = [
134+
[2, 6],
135+
[2, 2, 3],
136+
[3, 4]
137+
]
138+
self.assertEqual(sorted(get_factors(target2)), sorted(answer2))
139+
self.assertEqual(sorted(get_factors(1)), [])
140+
self.assertEqual(sorted(get_factors(37)), [])
141+
142+
def test_recursive_get_factors(self):
143+
target1 = 32
144+
answer1 = [
145+
[2, 16],
146+
[2, 2, 8],
147+
[2, 2, 2, 4],
148+
[2, 2, 2, 2, 2],
149+
[2, 4, 4],
150+
[4, 8]
151+
]
152+
self.assertEqual(sorted(recursive_get_factors(target1)), sorted(answer1))
153+
154+
target2 = 12
155+
answer2 = [
156+
[2, 6],
157+
[2, 2, 3],
158+
[3, 4]
159+
]
160+
self.assertEqual(sorted(recursive_get_factors(target2)), sorted(answer2))
161+
self.assertEqual(sorted(recursive_get_factors(1)), [])
162+
self.assertEqual(sorted(recursive_get_factors(37)), [])
163+
164+
113165
class TestFindWords(unittest.TestCase):
114166

115167
def test_normal(self):
@@ -158,6 +210,21 @@ def test_repeat(self):
158210
self.assertTrue(len(find_words(board, words)) == 5)
159211

160212

213+
class TestGenerateAbbreviations(unittest.TestCase):
214+
def test_generate_abbreviations(self):
215+
word1 = "word"
216+
answer1 = ['word', 'wor1', 'wo1d', 'wo2', 'w1rd', 'w1r1', 'w2d', 'w3',
217+
'1ord', '1or1', '1o1d', '1o2', '2rd', '2r1', '3d', '4']
218+
self.assertEqual(sorted(generate_abbreviations(word1)), sorted(answer1))
219+
220+
word2 = "hello"
221+
answer2 = ['hello', 'hell1', 'hel1o', 'hel2', 'he1lo', 'he1l1', 'he2o',
222+
'he3', 'h1llo', 'h1ll1', 'h1l1o', 'h1l2', 'h2lo', 'h2l1', 'h3o', 'h4',
223+
'1ello', '1ell1', '1el1o', '1el2', '1e1lo', '1e1l1', '1e2o', '1e3',
224+
'2llo', '2ll1', '2l1o', '2l2', '3lo', '3l1', '4o', '5']
225+
self.assertEqual(sorted(generate_abbreviations(word2)), sorted(answer2))
226+
227+
161228
class TestPatternMatch(unittest.TestCase):
162229

163230
def test_pattern_match(self):
@@ -172,6 +239,7 @@ def test_pattern_match(self):
172239
self.assertTrue(pattern_match(pattern2, string2))
173240
self.assertFalse(pattern_match(pattern3, string3))
174241

242+
175243
class TestGenerateParenthesis(unittest.TestCase):
176244

177245
def test_generate_parenthesis(self):
@@ -180,7 +248,19 @@ def test_generate_parenthesis(self):
180248
self.assertEqual(generate_parenthesis_v2(2), ['(())', '()()'])
181249
self.assertEqual(generate_parenthesis_v2(3), ['((()))', '(()())', '(())()', '()(())', '()()()'])
182250

251+
252+
class TestLetterCombinations(unittest.TestCase):
253+
254+
def test_letter_combinations(self):
255+
digit1 = "23"
256+
answer1 = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
257+
self.assertEqual(sorted(letter_combinations(digit1)), sorted(answer1))
258+
259+
digit2 = "34"
260+
answer2 = ['dg', 'dh', 'di', 'eg', 'eh', 'ei', 'fg', 'fh', 'fi']
261+
self.assertEqual(sorted(letter_combinations(digit2)), sorted(answer2))
262+
263+
183264
if __name__ == '__main__':
184265

185266
unittest.main()
186-

0 commit comments

Comments
 (0)