-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathlongest_common_prefix.py
More file actions
114 lines (87 loc) · 3.12 KB
/
Copy pathlongest_common_prefix.py
File metadata and controls
114 lines (87 loc) · 3.12 KB
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
"""
Longest Common Prefix
Find the longest common prefix string amongst an array of strings.
Three approaches: horizontal scanning, vertical scanning, and divide and conquer.
Reference: https://leetcode.com/problems/longest-common-prefix/
Complexity:
Time: O(S) where S is the sum of all characters in all strings
Space: O(1) for iterative, O(m * log n) for divide and conquer
"""
from __future__ import annotations
def _common_prefix(first: str, second: str) -> str:
"""Return the common prefix of two strings.
Args:
first: The first string.
second: The second string.
Returns:
The common prefix shared by both strings.
"""
if not first or not second:
return ""
index = 0
while first[index] == second[index]:
index = index + 1
if index >= len(first) or index >= len(second):
return first[0:index]
return first[0:index]
def longest_common_prefix_v1(strings: list[str]) -> str:
"""Find longest common prefix using horizontal scanning.
Args:
strings: A list of strings to compare.
Returns:
The longest common prefix, or empty string if none exists.
Examples:
>>> longest_common_prefix_v1(["flower", "flow", "flight"])
'fl'
"""
if not strings:
return ""
result = strings[0]
for index in range(len(strings)):
result = _common_prefix(result, strings[index])
return result
def longest_common_prefix_v2(strings: list[str]) -> str:
"""Find longest common prefix using vertical scanning.
Args:
strings: A list of strings to compare.
Returns:
The longest common prefix, or empty string if none exists.
Examples:
>>> longest_common_prefix_v2(["flower", "flow", "flight"])
'fl'
"""
if not strings:
return ""
for index in range(len(strings[0])):
for string in strings[1:]:
if index == len(string) or string[index] != strings[0][index]:
return strings[0][0:index]
return strings[0]
def longest_common_prefix_v3(strings: list[str]) -> str:
"""Find longest common prefix using divide and conquer.
Args:
strings: A list of strings to compare.
Returns:
The longest common prefix, or empty string if none exists.
Examples:
>>> longest_common_prefix_v3(["flower", "flow", "flight"])
'fl'
"""
if not strings:
return ""
return _longest_common_recursive(strings, 0, len(strings) - 1)
def _longest_common_recursive(strings: list[str], left: int, right: int) -> str:
"""Recursively find the longest common prefix using divide and conquer.
Args:
strings: The list of strings.
left: The left index of the current partition.
right: The right index of the current partition.
Returns:
The longest common prefix for the partition.
"""
if left == right:
return strings[left]
mid = (left + right) // 2
lcp_left = _longest_common_recursive(strings, left, mid)
lcp_right = _longest_common_recursive(strings, mid + 1, right)
return _common_prefix(lcp_left, lcp_right)