Coverage for blog/dsa/leetcode/palindrome_shortest/__init__.py: 47%

1import pytest 

2 

3 

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

14 

15 stop, start = index, index 

16 if even: 

17 if stop == index_final: 

18 return start, start 

19 

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) 

26 

27 for _ in range(delta): 

28 start -= 1 

29 stop += 1 

30 

31 if s[start] != s[stop]: 

32 start += 1 

33 stop -= 1 

34 break 

35 

36 return start, stop 

37 

38 def shortestPalindrome(self, s: str) -> str: 

39 n = len(s) 

40 if n == 1: 

41 return s 

42 

43 index_final = n - 1 

44 best_initial, best_terminal = 0, index_final 

45 

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 

62 

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 

75 

76 size_terminal = index_final - best_terminal 

77 size_initial = best_initial 

78 

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] 

87 

88 # stop snippit solution_initial 

89 

90 

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] 

101 

102 def shortestPalindrome(self, s: str): 

103 

104 n = len(s) 

105 if not n: 

106 return s 

107 

108 index_final = n - 1 

109 char_init, char_term = s[0], s[-1] 

110 best_init, best_term = 0, index_final 

111 

112 if self.isPalindrome(s, 0, n - 1): 

113 return s 

114 

115 for index in range(n - 1): 

116 char_front = s[index] 

117 char_back = s[index_final - index] 

118 

119 if ( 

120 char_front == char_init 

121 and self.isPalindrome(s, 0, index) 

122 # and index > best_init 

123 ): 

124 best_init = index 

125 

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 

132 

133 size_terminal = index_final - best_term 

134 size_initial = best_init 

135 

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] 

144 

145 # end snippet solution 

146 

147 

148@pytest.fixture 

149def solution(): 

150 return Solution() 

151 

152 

153big = 10 * "a" 

154 

155 

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

173 

174 answer_computed = solution.shortestPalindrome(question) 

175 if len(answer) < 1000: 

176 # print(answer_computed, answer) 

177 pass 

178 assert answer_computed == answer 

179 

180 

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

191 

192 n = len(question) 

193 assert solution.isPalindrome(question, 0, n) == answer