214. Shortest Palindrome

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "aacecaaa"

Output: "aaacecaaa"

Example 2

Input: "abcd"

Output: "dcbabcd"

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String shortestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;
        
        int i = 0, j = s.length();
        
        while(j-- > 0) {
            if(s.charAt(i) == s.charAt(j)) {
                i++;
            }
        }
        
        if(i == s.length()) return s;
        
        String suffix = s.substring(i);
        String prefix = new StringBuilder(suffix).reverse().toString();
        
        return prefix + shortestPalindrome(s.substring(0, i)) + suffix;
    }
}

Follow up