Coverage for blog/dsa/leetcode/longest_pfx/__init__.py: 77%
94 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1from typing import Any
3import pytest
4from typing_extensions import Self
7# start snippet solution_trivial
8class SolutionTrivial:
10 def pfx_elems(self, a: str, b: str) -> int:
12 count = 0
13 for char_a, char_b in zip(a, b):
14 if char_a != char_b:
15 break
17 count += 1
19 return count
21 def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
23 size_biggest = 0
25 for a in map(str, sorted(arr1, reverse=True)):
26 if len(a) <= size_biggest:
27 break
29 for b in map(str, arr2):
30 size = self.pfx_elems(a, b)
31 if size > size_biggest:
32 size_biggest = size
34 return size_biggest
35 # end snippet solution_trivial
38# start snippet trie
39# start snippet trie_min
40class TrieNode:
41 terminates: int
42 children: dict[str, Self]
44 def __init__(
45 self,
46 children: dict[str, Self],
47 terminates: int = False,
48 ):
49 self.children = children
50 self.terminates = terminates
52 # end snippet trie_min
54 def toDict(self, depth=None, *, _depth: int = 0) -> dict[str, Any]:
56 out: dict[str, Any] = dict()
58 if self.terminates:
59 out["terminates"] = self.terminates
61 if depth is None or _depth < depth:
62 out.update(
63 {
64 char: node.toDict(depth, _depth=_depth + 1)
65 for char, node in self.children.items()
66 }
67 )
68 return out
70 def insert(self, val: str):
72 node = self
73 for char in val:
74 if char not in node.children:
75 node_new = self.__class__(dict())
76 node.children[char] = node_new
77 node = node_new
78 else:
79 node = node.children[char]
81 node.terminates += 1
82 return
84 def get(self, val: str) -> Self | None:
85 node = self
86 for char in val:
87 if char not in node.children:
88 return None
89 node = node.children[char]
91 return node
93 def prefix(self, val: str) -> int:
95 node, pfx = self, 0
97 for char in val:
98 if char not in node.children:
99 return pfx
101 pfx += 1
102 node = node.children[char]
104 return pfx
105 # end snippet trie
108# start snippet solution
109class Solution:
110 def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
111 root = TrieNode(dict())
113 for s in map(str, arr1):
114 root.insert(s)
116 size_max = 0
118 arr2.sort(reverse=True)
119 for s in map(str, arr2):
120 if len(s) <= size_max:
121 break
123 size = root.prefix(s)
124 size_max = max(size, size_max)
126 return size_max
127 # end snippet soltion
130@pytest.fixture
131def solution():
132 return Solution()
135@pytest.mark.parametrize(
136 "arr1, arr2, answer",
137 (
138 ([1, 10, 100], [1000], 3),
139 ([1, 2, 3], [4, 4, 4], 0),
140 ),
141)
142def test_solution(solution: Solution, arr1: list[int], arr2: list[int], answer: int):
144 answer_computed = solution.longestCommonPrefix(arr1, arr2)
145 assert answer == answer_computed
148def test_trie():
150 root = TrieNode(dict())
151 assert not root.get("a")
153 root.insert("a")
154 assert root.get("a")
155 assert "a" in root.children
156 assert not len(root.children["a"].children)
158 root.insert("aardvark")
159 root.insert("alameda")
160 root.insert("alphabetical")
162 assert root.get("a") and root.get("aardvark")
163 assert root.get("alameda") and root.get("alphabetical")
164 assert not root.get("aa").terminates and not root.get("al").terminates
166 assert root.prefix("alaverga") == 3
167 assert root.prefix("aa") == 2