diff options
Diffstat (limited to 'find_len_longest_prefix.py')
-rw-r--r-- | find_len_longest_prefix.py | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/find_len_longest_prefix.py b/find_len_longest_prefix.py new file mode 100644 index 0000000..821e911 --- /dev/null +++ b/find_len_longest_prefix.py @@ -0,0 +1,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])) |