214. Shortest Palindrome

Description

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.

 

Solutions

Solution: String Matching

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const shortestPalindrome = function (s) {
  const n = s.length;
  const reverseS = s.split('').reverse().join('');

  for (let index = 0; index < n; index++) {
    const sliceReverseS = reverseS.slice(index);
    const sliceS = s.slice(0, n - index);

    if (sliceReverseS !== sliceS) continue;
    return `${reverseS.slice(0, index)}${s}`;
  }
  return s;
};