Java solution inspired from others


  • 0
    Z
    public static String shortestPalindrome(String s) {
      if (s == null || s.length() < 2) return s;
    
      String result = null;
      for (int i = s.length() / 2; i >= 1; i--) {
          // check if it is double character centered 
          result = getPalindromeFromCenter(s, i - 1, i);
          if (result != null) break;
      
          // check if it is single character centered
          result = getPalindromeFromCenter(s, i - 1, i - 1);
          if (result != null) break;
      }
    
      return result;
    }
    
    private static String getPalindromeFromCenter(String str, int start, int end) {
        //scan from center to both sides
        while (start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end)) {
            --start;
            ++end;
        }
     
        //if not end at the beginning of s, return null 
        if (start >= 0) return null;
     
        StringBuilder sb = new StringBuilder(str.substring(end));
        sb.reverse();
     
        return sb.append(str).toString();
    }

  • 0
    Z

    Well, the complexity is still O(n^2) so it is no better than brute force asymptotically. But it can pass the edge test. A bit tricky. :)


  • 0
    C

    The test cases do not cover all edge cases.

    This solution fails with input "aba". It returns "ababa" instead of "aba"


  • 0
    D

    Its because his cases are inverted, double character palindrome is larger than a single middle character palindrome in pretty much every case.


  • 0

    Thanks @codenh, I have added your test case.


Log in to reply
 

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