aboutsummaryrefslogtreecommitdiff
path: root/find_len_longest_prefix.py
blob: 821e911afc0cb42c7d46a6b7a078f9223f546ffe (plain)
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
# 3043. Find the Length of the Longest Common Prefix
from bisect import bisect_left

"""
given two arrays with positive integers 'arr1' and 'arr2'. a prefix of a
positive integer is an integer formed by one or more of its digits, starting
from its leftmost digit. a common prefix of two integers 'a' and 'b' is an
integer 'c' such that is a prefix of both a and b. for example 6555359 and
56554 have a common prefix 565 while q223 and 43456 do not have a common
prefix. return the length of the longest common prefix among all pairs. if no
common prefix exists among them, return 0.
"""


class Solution(object):
    def longestCommonPrefix(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: int
        """

        def findCommonPrefixLength(x, y):
            common_prefix_length = 0
            min_length = min(len(x), len(y))

            for i in range(min_length):
                if x[i] == y[i]:
                    common_prefix_length += 1
                else:
                    break

            return common_prefix_length

        a = [str(x) for x in arr1]
        b = [str(x) for x in arr2]

        a.sort()
        b.sort()

        ans = 0
        n = len(a)
        for i in range(len(b)):
            idx = bisect_left(a, b[i])
            if idx < n:
                ans = max(ans, findCommonPrefixLength(a[idx], b[i]))
            if idx > 0:
                ans = max(ans, findCommonPrefixLength(a[idx - 1], b[i]))
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.longestCommonPrefix(arr1=[1, 10, 100], arr2=[1000]))
    print(obj.longestCommonPrefix(arr1=[1, 2, 3], arr2=[4, 4, 4]))