Coverage for blog/dsa/leetcode/longest_pfx/__init__.py: 77%

1from typing import Any 

2 

3import pytest 

4from typing_extensions import Self 

5 

6 

7# start snippet solution_trivial 

8class SolutionTrivial: 

9 

10 def pfx_elems(self, a: str, b: str) -> int: 

11 

12 count = 0 

13 for char_a, char_b in zip(a, b): 

14 if char_a != char_b: 

15 break 

16 

17 count += 1 

18 

19 return count 

20 

21 def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int: 

22 

23 size_biggest = 0 

24 

25 for a in map(str, sorted(arr1, reverse=True)): 

26 if len(a) <= size_biggest: 

27 break 

28 

29 for b in map(str, arr2): 

30 size = self.pfx_elems(a, b) 

31 if size > size_biggest: 

32 size_biggest = size 

33 

34 return size_biggest 

35 # end snippet solution_trivial 

36 

37 

38# start snippet trie 

39# start snippet trie_min 

40class TrieNode: 

41 terminates: int 

42 children: dict[str, Self] 

43 

44 def __init__( 

45 self, 

46 children: dict[str, Self], 

47 terminates: int = False, 

48 ): 

49 self.children = children 

50 self.terminates = terminates 

51 

52 # end snippet trie_min 

53 

54 def toDict(self, depth=None, *, _depth: int = 0) -> dict[str, Any]: 

55 

56 out: dict[str, Any] = dict() 

57 

58 if self.terminates: 

59 out["terminates"] = self.terminates 

60 

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 

69 

70 def insert(self, val: str): 

71 

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] 

80 

81 node.terminates += 1 

82 return 

83 

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] 

90 

91 return node 

92 

93 def prefix(self, val: str) -> int: 

94 

95 node, pfx = self, 0 

96 

97 for char in val: 

98 if char not in node.children: 

99 return pfx 

100 

101 pfx += 1 

102 node = node.children[char] 

103 

104 return pfx 

105 # end snippet trie 

106 

107 

108# start snippet solution 

109class Solution: 

110 def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int: 

111 root = TrieNode(dict()) 

112 

113 for s in map(str, arr1): 

114 root.insert(s) 

115 

116 size_max = 0 

117 

118 arr2.sort(reverse=True) 

119 for s in map(str, arr2): 

120 if len(s) <= size_max: 

121 break 

122 

123 size = root.prefix(s) 

124 size_max = max(size, size_max) 

125 

126 return size_max 

127 # end snippet soltion 

128 

129 

130@pytest.fixture 

131def solution(): 

132 return Solution() 

133 

134 

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): 

143 

144 answer_computed = solution.longestCommonPrefix(arr1, arr2) 

145 assert answer == answer_computed 

146 

147 

148def test_trie(): 

149 

150 root = TrieNode(dict()) 

151 assert not root.get("a") 

152 

153 root.insert("a") 

154 assert root.get("a") 

155 assert "a" in root.children 

156 assert not len(root.children["a"].children) 

157 

158 root.insert("aardvark") 

159 root.insert("alameda") 

160 root.insert("alphabetical") 

161 

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 

165 

166 assert root.prefix("alaverga") == 3 

167 assert root.prefix("aa") == 2