目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"

示例 2:

输入: "abcd"
输出: "dcbabcd"

二、解题思路

1.由于是在前面添加字符，因此需要从后往前寻找合适的字符串逆序然后添加到原字符串前面。

2.可以构造逆序的字符串，然后寻找与原字符串相等的回文部分，然后直接把逆序的字符串被过滤掉的部分添加在原字符串前即可构成回文字符串。

三、代码

  

   

    

     

    
    

     

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

    

     

    
    

     
 break
     
    
   

    

     

    
    

     

       add_before = s2[:i]
     
    
   

    

     

    
    

     

       new_s = add_before + s
     
    
   

    

     

    
    

     
 return new_s
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       test = "aaacecaa"
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.shortestPalindrome(test)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108293132