Using longest beginning palindrome, 200ms


  • 0
    R
    public class Solution {
        public String shortestPalindrome(String s) {
            char[] arr = s.toCharArray();
            StringBuilder copy = new StringBuilder(s);
            for (int i = s.length()-1; i > -1; i--) {
                if (isPalindrome(arr, 0, i)) {
                    StringBuilder end = new StringBuilder(s.substring(i+1));
                    copy.insert(0, end.reverse());
                    return copy.toString();
                }
            }
            return "";
        }
        
        private boolean isPalindrome(char[] arr, int i, int j) {
            for (; i < j; i++) {
                if (arr[i]!=arr[j]) return false;
                j--;
            }
            return true;
        }
    }
    

Log in to reply
 

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