[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

	class Solution {
	fun shortestPalindrome(s: String): String {
	var left = 0
	var right = s.lastIndex
	var end = s.lastIndex
	while (left < right) {
	if (s[left] == s[right]) {
	++left
	--right
	} else {
	left = 0
	--end
	right = end
	}
	}
	return s.substring(end+1).reversed() + s
	}
	}

view raw shortest_palindrome.kt hosted with ❤ by GitHub