Any idea why this got a TLE?


  • 0
    S

    My code got a tle with the super long "aaaaaaaa" string. Any idea why this fails? Might be double to int cast? And any idea to fix? thanks.

     public class Solution {
        public String shortestPalindrome(String s) {
            double midpoint = (s.length() - 1) / 2.0;
            for(double i = midpoint; i >= 0; i -= 0.5) {
                
                if(isValid(s, i)) {
                    return formString(s, i);
                }
            }
            return null;
        }
        
        private boolean isValid(String s, double midPoint) {
            
            for(int i = 0; i < midPoint; i++) {
                if (s.charAt(i) != s.charAt((int)(2 * midPoint - i))) {
                    return false;
                } 
            }
            return true;
        }
        
        private String formString(String s, double midPoint) {
            if(s.length() - 1 == midPoint * 2) {
                return s;
            }
            StringBuffer prefix = new StringBuffer(); 
            for(int i = s.length() - 1; i > 2 * midPoint; i --) {
                prefix.append(s.charAt(i));
            }
            prefix.append(s);
            return prefix.toString();
        }
    }

  • 0
    V

    At least you do not need to go though all array in your method isValid. Just take left and right sides and equal them. It is good for performance but I think it won't help


Log in to reply
 

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