Brute Force Solution #Java #longest-palindrome-prefix


  • 0

    This is a straightforward Java solution via finding the longest palindrome prefix. I don't think I can come out with the KMP solution or the magical recursive solution during the interview, so I post what I would write here.

    public class Solution {
        public String shortestPalindrome(String s) {
            if (s == null || s.isEmpty()) return s;
    
            int maxIndex = 0;
            for(int i=s.length()-1; i>=0; --i) {
                if (_isPalindrome(s, 0, i)) {
                    maxIndex = i;
                    break;
                }
            }
    
            if (maxIndex == s.length()-1) return s;
    
            StringBuilder sb = new StringBuilder(s.substring(maxIndex+1, s.length()));
            return sb.reverse().append(s).toString();
        }
    
        private boolean _isPalindrome(String s, int l, int r){
            if (s == null || s.isEmpty()) return true;
    
            while(l <= r) {
                if (s.charAt(l++) != s.charAt(r--)) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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