Coverage for blog/dsa/leetcode/palindrome_shortest/__init__.py: 47%
92 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
1import pytest
4# start snippit solution_initial
5class SolutionInitial:
6 def searchPalindrome(
7 self,
8 s: str,
9 *,
10 index_final: int,
11 index: int,
12 even: bool = False,
13 ):
15 stop, start = index, index
16 if even:
17 if stop == index_final:
18 return start, start
20 stop += 1
21 if s[start] != s[stop]:
22 return start, start
23 delta = min(index_final - 1 - index, index)
24 else:
25 delta = min(index_final - index, index)
27 for _ in range(delta):
28 start -= 1
29 stop += 1
31 if s[start] != s[stop]:
32 start += 1
33 stop -= 1
34 break
36 return start, stop
38 def shortestPalindrome(self, s: str) -> str:
39 n = len(s)
40 if n == 1:
41 return s
43 index_final = n - 1
44 best_initial, best_terminal = 0, index_final
46 for index in range(n):
47 start, stop = self.searchPalindrome(
48 s,
49 index_final=index_final,
50 index=index,
51 even=False,
52 )
53 start_even, stop_even = self.searchPalindrome(
54 s,
55 index_final=index_final,
56 index=index,
57 even=True,
58 )
59 if start_even <= start and stop_even >= stop:
60 start = start_even
61 stop = stop_even
63 # NOTE: If a palindrome is found that is the entire string, return
64 # the entire string. When the stop is is n, a terminal
65 # palindrome is found When the start point is 0, an initial
66 # palindrome is found.
67 if start != 0 and stop != n:
68 continue
69 elif start == 0 and stop == n:
70 return s
71 elif start == 0 and stop > best_initial:
72 best_initial = stop
73 elif stop == index_final and start < best_terminal:
74 best_terminal = start
76 size_terminal = index_final - best_terminal
77 size_initial = best_initial
79 if size_initial >= size_terminal:
80 palindrome = s[: best_initial + 1]
81 mantisa = s[best_initial + 1 :]
82 return mantisa[::-1] + palindrome + mantisa
83 else:
84 palindrome = s[best_terminal:]
85 mantisa = s[:best_terminal]
86 return mantisa + palindrome + mantisa[::-1]
88 # stop snippit solution_initial
91# start snippet solution
92class Solution:
93 def isPalindrome(
94 self,
95 s: str,
96 start: int,
97 stop: int,
98 ):
99 t = s[start : stop + 1]
100 return t == t[::-1]
102 def shortestPalindrome(self, s: str):
104 n = len(s)
105 if not n:
106 return s
108 index_final = n - 1
109 char_init, char_term = s[0], s[-1]
110 best_init, best_term = 0, index_final
112 if self.isPalindrome(s, 0, n - 1):
113 return s
115 for index in range(n - 1):
116 char_front = s[index]
117 char_back = s[index_final - index]
119 if (
120 char_front == char_init
121 and self.isPalindrome(s, 0, index)
122 # and index > best_init
123 ):
124 best_init = index
126 if (
127 char_back == char_term
128 and self.isPalindrome(s, index_final - index, index_final)
129 # and index < best_term
130 ):
131 best_term = index_final - index
133 size_terminal = index_final - best_term
134 size_initial = best_init
136 if size_initial >= size_terminal:
137 palindrome = s[: best_init + 1]
138 mantisa = s[best_init + 1 :]
139 return mantisa[::-1] + palindrome + mantisa
140 else:
141 palindrome = s[best_term:]
142 mantisa = s[:best_term]
143 return mantisa + palindrome + mantisa[::-1]
145 # end snippet solution
148@pytest.fixture
149def solution():
150 return Solution()
153big = 10 * "a"
156@pytest.mark.parametrize(
157 "question, answer",
158 (
159 ("a", "a"),
160 ("ab", "bab"),
161 ("aacecaaa", "aaacecaaa"),
162 ("abcd", "dcbabcd"),
163 ("aac", "caac"),
164 ("kcaaffaack", "kcaaffaack"),
165 ("aa", "aa"),
166 (
167 (big + "c" + big + "d" + big),
168 (big + "d" + big + "c" + big + "d" + big),
169 ),
170 ),
171)
172def test_solution(solution: Solution, question: str, answer: str):
174 answer_computed = solution.shortestPalindrome(question)
175 if len(answer) < 1000:
176 # print(answer_computed, answer)
177 pass
178 assert answer_computed == answer
181@pytest.mark.parametrize(
182 "question, answer",
183 (
184 ("aa", True),
185 ("abbbbba", True),
186 ("", True),
187 (10**1 * "a", True),
188 ),
189)
190def test_is_palindrome(solution: Solution, question: str, answer: bool):
192 n = len(question)
193 assert solution.isPalindrome(question, 0, n) == answer