目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: \”aacecaaa\”
输出: \”aaacecaaa\”
示例 2:
输入: \”abcd\”
输出: \”dcbabcd\”
二、解题思路
1.由于是在前面添加字符,因此需要从后往前寻找合适的字符串逆序然后添加到原字符串前面。
2.可以构造逆序的字符串,然后寻找与原字符串相等的回文部分,然后直接把逆序的字符串被过滤掉的部分添加在原字符串前即可构成回文字符串。
三、代码
[code]class Solution:def shortestPalindrome(self, s: str) -> str:length = len(s)if length == 0:return \"\"s2 = s[::-1]for i in range(length):if s2[i:] == s[:length - i]:breakadd_before = s2[:i]new_s = add_before + sreturn new_sif __name__ == \'__main__\':test = \"aaacecaa\"s = Solution()ans = s.shortestPalindrome(test)print(ans)
悲恋花丶无心之人CSDN认证博客专家TensorFlow深度学习神经网络计算机视觉在读研究生,熟悉Pytorch,MXNet,TensorFlow,Keras等深度学习框架,主要涉及的领域有目标检测,语义分割,超分辨率重建,行人重识别等。