Easy to understand java solution


  • 0
    M

    The concept is really simple. I check for palindrome that includes the first character in the string. Then, I copy the rest of the string and reverse it and attach it to the beginning of the string.
    For ex:
    Consider the string "abbacd"
    I check the palindrome that can be formed using the first character. In this case 'a', the palindrome is "abba". Now i copy the rest of the string "cd" and reverse it "dc" and append it to the front of the string. Hence we get, "dcabbacd".
    Another example,
    Consider the string "aacecaaa".
    I check the palindrome that can be formed that involves the first character, which is "aacecaa", then I get the rest of the string "a" and reverse it "a" and append it to the front of the string. "aaacecaaa".
    Consider the string "abcd"
    There is no palindrome that involves "a" except the string "a", so I inverse the rest of the string "bcd" becomes "dcb" and attach it to the front. "dcbabvd".
    This is a O(n^2) solution, but it is easy to understand.

    public class Solution {
        public String shortestPalindrome(String s) {
            if(s.length()==0){
                return "";
            }
            if(checkPalindrome(s,0,s.length()-1)){
                return s;
            }
            int i=0, last=s.length()-2;
            
            while(i<=s.length()){
                if(checkPalindrome(s,i,last)){
                    String sb = new StringBuilder(s.substring(last+1,s.length())).reverse().toString();
                    return sb+s;
                }
                last--;
            }
            return s;
        }
        public boolean checkPalindrome(String s, int i,int k){
            //int k=s.length()-1;
            while(i<k){
                if(s.charAt(i)==s.charAt(k)){
                    i++;k--;
                }else{
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.