Not sure why it is hard category. Simple JAVA code


  • 0
    I
    public class Solution {
        public String shortestPalindrome(String s) {
            
            if(canBePal(s, 0, s.length() - 1) || s.isEmpty()) {
                return s;
            }
            
            for(int i = s.length() - 2; i > 0; i--) {
                if(canBePal(s, 0, i)) {
                    String pref = s.substring(i + 1, s.length());
                    return reverse(pref) + s;
                }
            }
            
            return reverse(s.substring(1, s.length())) + s;
        }
        
        String reverse(String s) {
            char[] data = s.toCharArray();
            int i = 0, j = data.length - 1;
            while(i < j) {
                char c = data[i];
                data[i] = data[j];
                data[j] = c;
                i++;
                j--;
            }
            
            return new String(data);
        }
        
        boolean canBePal(String s, int beg, int end) {
            while(beg < end) {
                if(s.charAt(beg) != s.charAt(end)) {
                    return false;
                }
                
                beg++;
                end--;
            }
            
            return true;
        }
    }
    

  • 0

    It's harder to do efficiently. I tried yours three times, twice it got about 390 ms and once it even got Time Limit Exceeded, so it's not really a good solution. The most common Java time is 4 ms.


  • 0
    I

    @StefanPochmann Can you elaborate more on better versions? I am curious about those now, what's their time complexity? Can you point to any implementations?


  • 1

    @ilakhmedov Check out the top-voted solutions?


Log in to reply
 

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