Force deduction longest palindrome substring Python -- sometimes DFS is better than DP

Given first dp Code for (clock It is a time measuring class written by myself )

class solution:
def longestPalindrome(self, s: str) -> str:
str_len = len(s)
index = 0
pace = 0
dp = [[0 for _ in s] for _ in s]
for idx in range(str_len):
dp[idx][idx] = 1
for idx in range(str_len - 1):
if s[idx] == s[idx + 1]:
dp[idx][idx + 1] = 1
if pace < 1:
pace = 1
index = idx
for p in range(2, str_len):
for left in range(str_len):
for right in range(left + p, str_len):
if s[left] == s[right]:
if dp[left + 1][right - 1]:
dp[left][right] = 1
if pace < p:
pace = p
index = left
return s[index: index + pace + 1]
temp = solution()
print(*clock(temp.longestPalindrome, test).result)

dp I won't talk about the specific train of thought , After all, the performance in this question is very poor , For length 800 + Evaluation data ,dp The time spent is about 8.5 s above , But a good pruner dfs But it only takes less than 0.1 s Time for

dfs The code framework of is as follows . Definition val Function to determine whether it is a palindrome string , the second for The loop is set to range(left + pace) That is, only search for better States than the current selection

str_len = len(s)
index = 0
pace = 0
# pace: Step size refers to right- left
for left in range(str_len):
for right in range(left + pace + 1, str_len):
if val(left, right):
if right - left > pace:
pace = right - left
index = left
return s[index: index + pace + 1]

and val The function is written as follows , The idea is left and right The two pointers lean towards the middle , Is it the same to proofread characters while leaning

def val(left, right):
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return False
return True

For a rookie like me who just wants to play in the Blue Bridge Cup , It would be nice to be able to pass