[LeetCode] 214. Shortest Palindrome

 轉自LeetCode

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

 

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

Solution

這題是要找，在原本的字串上，加上最少的字元，可以變成一個回文串

解題想法如下

因為題目有規定，只能在原本字串的前面插入字元

所以如果字串本身就是回文串，那就傳回原本的字串

但如果有插入字元，原本字串的開頭，就只會是回文串的一部份

因此，先在原本字串中，找到最長的回文串，開頭都是從原本的字串頭開始

找到之後，把不在回文串裡面的字串們，反轉插入到前方，就可以找到答案了

code 如下

kotlin