268ms brute force method but easily to understand


  • 0
    G

    simply check from the middle.

    public class Solution {
        public String shortestPalindrome(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }
            for (int i = (s.length() + 1) / 2 - 1; i >= 0 ; i--) {
                if (checkEven(s, i)) {
                    return new StringBuilder(s.substring(i + 1, s.length())).reverse().append(s.substring(i + 1, s.length())).toString();
                }
                if (checkOdd(s, i)) {
                    return new StringBuilder(s.substring(i + 1, s.length())).reverse().append(s.substring(i, s.length())).toString();
                }
            }
            return new StringBuilder(s.substring(1, s.length())).reverse().append(s).toString();
        }
        
        public boolean checkOdd(String s, int index) {
            for (int j = 1; index - j >= 0; j++) {
                if (s.charAt(index - j) != s.charAt(index + j)) {
                    return false;
                }
            }
            return true;
        }
        
        public boolean checkEven(String s, int index) {
            for (int j = 0; index - j >= 0; j++) {
                if (index + 1 + j >= s.length()) {
                    return false;
                }
                if (s.charAt(index - j) != s.charAt(index + 1 + j)) {
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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