Given a string s, convert it into a palindrome

3.82K viewsAlgorithmsalgorithms palindrome string substring
0

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa" 
Output:"aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"
Answered question
0
LittleJohn (anonymous) 0 Comments

There are different edge cases we want to tackle in this sort of a problem

 

  1. Check if the string contains all non-repeating characters, if that’s the case, prefix last N-1 characters from the string of length N in front of the string

 

    2. If first criteria isn’t met, check the indices which differ in values in the string and save the first index. Reverse the sub-string ahead of this pivot and append the original string S to this substring obtained.

 

     3. If both the above isn’t the case, then loop through the string in the reverse order, and append character/s one by one to a new string and append the original string to the new string and check for palindrome in the loop, if it’s  palindrome, return it else continue looping.

 

Javascript code below

 

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
 if (isPallindrome(s)) return s;
  var match = s.match(/(?=^[A-Za-z0-9]+$)(.)+.*\1.*/g);
 if (!match) {
  return s.substring(1).split('').reverse().join('') + s;
 }
   var pivot = -1;
  for (var ii = 0; ii < s.length; ii++) {
  if (s[ii] !== s[ii + 1]) {
   pivot = ii;
   break;
  }
 }
 var string = s.substr(pivot + 1);
  var rem = string.split('').reverse().join('');
  if (pivot + 1 === Math.floor((s.length - 1) / 2))
  return rem + s;
   var preset = '';
  for (var i = s.length - 1; i >= 0; i--) {
  preset += s[i];
  var str = preset + s;
  if (isPallindrome(str))
   return str;
 }
};
  var isPallindrome = function(strng) {
 return [...strng].reverse().join('') === strng;
};

 

Changed status to publish
Write your answer.

Categories