-
Notifications
You must be signed in to change notification settings - Fork 7
/
0014.py
47 lines (40 loc) · 1.26 KB
/
0014.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
from functools import reduce
class Solution:
#
# Total 2 approaches are intorduced.
#
# Complexity: O(mn), where m is length of the longest common prefix.
#
# First: Pythonic golfing.
#
def longestCommonPrefix(self, strs):
s, z = "", zip(*strs)
# Read strs "matrix" column by column
for k in z:
if len(set(k)) > 1:
break
s += k[0]
return s
#
# Second: Step-and-Compare.
#
def cmpTwoStrs(self, str1, str2):
i, n = 0, min(len(str1), len(str2))
while i < n and str1[i] == str2[i]:
i += 1
return str1[:i]
def longestCommonPrefix2(self, strs):
# from functools import reduce
return reduce(self.cmpTwoStrs, strs) if strs else ""
# TEST ONLY
import unittest
class TestConvert(unittest.TestCase):
def test_equal(self):
func = Solution().longestCommonPrefix
self.assertEqual(func(["abeyd", "ab", "abc", "abed"]), "ab")
self.assertEqual(func(["a", "", "ge"]), "")
func2 = Solution().longestCommonPrefix2
self.assertEqual(func2(["abeyd", "ab", "abc", "abed"]), "ab")
self.assertEqual(func2(["a", "", "ge"]), "")
if __name__ == "__main__":
unittest.main()