Java brute force method passes oj in 56 ms.


  • 0
    F

    Java brute force solution passes oj with 56ms.
    A few tweaks I did:

    1. When trying to match the prefix with the part after the folding point, use two pointers to compare characters one by one, instead of reversing the prefix and call startsWith
    2. Start from the middle and as long as a solution is found, it must be the shortest palindrome, because as we move i to the left from the middle, the more characters we will need to patch at the beginning.
    public class Solution {
        public String shortestPalindrome(String s) {
            if (s.length() < 2) { return s; }
            for (int i = s.length() / 2; i >= 0; i--) {
                int index = checkPalindromeEqual(s, i - 1, i + 1);
                if (index != -1) {
                    return new StringBuilder(s.substring(index)).reverse().append(s).toString();
                } else {
                    index = checkPalindromeEqual(s, i - 1, i);
                    if (index != -1) {
                        return new StringBuilder(s.substring(index)).reverse().append(s).toString();
                    } else {
                        continue;
                    }
                }
            }
            //Won`t reach here.
            return new StringBuilder(s.substring(1)).reverse().append(s).toString();
        }
    
        private int checkPalindromeEqual(String s, int i, int j) {
            //To avoid cases like "ab"
            if (j == s.length()) { return -1; }
            while(i >= 0 && j < s.length()) {
                if (s.charAt(i) == s.charAt(j)) {
                    i--;
                    j++;
                } else {
                    return -1;
                }
            }
            return j;
        }
    }
    

Log in to reply
 

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