Java solution got TLE at last case for no reason. PLEASE CHECK OJ.


  • 0
    S

    PLEASE CHECK OJ

    For example, this is my solution for "Longest Palindromic Substring ". But this is O(n) manacher solution.

    public class Solution {
        static int [] p = new int [1010];
    
        public String longestPalindrome(String s) {
            s = "#" + String.join("#", s.split("")) + "#";
            int n = s.length();
    
            if(n == 0) return "";
    
            int maxp = 0, pos = 0, ret = 0;
    
            for(int i = 0; i < n; ++i) {
                if(i < maxp) p[i] = Math.min(p[2 * pos - i], maxp - i);
                else p[i] = 1;
    
                while(i - p[i] >= 0 && i + p[i] < n &&
                        s.charAt(i - p[i]) == s.charAt(i + p[i]))
                    ++p[i];
    
                if(p[i] + i - 1 > maxp) {
                    maxp = p[i] + i - 1;
                    pos = i;
                }
    
                if(p[i] > p[ret] || (p[i] == p[ret] && s.charAt(i) != '#')) ret = i;
            }
    
            // System.out.println(ret + " " + p[ret] + " " + s);
            // for(int x : p) System.out.println(x);
            String ans = s.substring(ret - p[ret] + 1, ret + p[ret]);
            // System.out.println(ans + " " + ret + " " + p[ret] + " " + s);
            ans = ans.replace("#", "");
            return ans;
        }
    }
    

    And for problem String to Integer (atoi) , here is my solution.

    public class Solution {
        public int myAtoi(String str) {
            str = str.replaceAll("^ *", "");
            if(str.length() == 0) return 0;
            System.out.println(str);
            boolean negative = false;
            int start = 0, end = -1;
            if(str.charAt(0) == '+' || str.charAt(0) == '-') {
                negative = str.charAt(0) == '-';
                start = 1;
            }
            for(end = start; end < str.length(); ++end)
                if(!Character.isDigit(str.charAt(end))) break;
            str = str.substring(start, end);
            System.out.println(str);
    
            try {
                if(str.length() == 0) return 0;
                return Integer.parseInt((negative ? "-" : "") + str);
            } catch(Exception e) {
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
        }
    }
    

    Both soluton got TLE at last case, but run code tells me the actual time is only about 40ms.


  • 0
    S

    @smallrqnoj said in Java solution got TLE at last case for no reason. PLEASE CHECK OJ.:

    PLEASE CHECK OJ

    For example, this is my solution for "Longest Palindromic Substring ". But this is O(n) manacher solution.

    public class Solution {
        static int [] p = new int [1010];
    
        public String longestPalindrome(String s) {
            s = "#" + String.join("#", s.split("")) + "#";
            int n = s.length();
    
            if(n == 0) return "";
    
            int maxp = 0, pos = 0, ret = 0;
    
            for(int i = 0; i < n; ++i) {
                if(i < maxp) p[i] = Math.min(p[2 * pos - i], maxp - i);
                else p[i] = 1;
    
                while(i - p[i] >= 0 && i + p[i] < n &&
                        s.charAt(i - p[i]) == s.charAt(i + p[i]))
                    ++p[i];
    
                if(p[i] + i - 1 > maxp) {
                    maxp = p[i] + i - 1;
                    pos = i;
                }
    
                if(p[i] > p[ret] || (p[i] == p[ret] && s.charAt(i) != '#')) ret = i;
            }
    
            // System.out.println(ret + " " + p[ret] + " " + s);
            // for(int x : p) System.out.println(x);
            String ans = s.substring(ret - p[ret] + 1, ret + p[ret]);
            // System.out.println(ans + " " + ret + " " + p[ret] + " " + s);
            ans = ans.replace("#", "");
            return ans;
        }
    }
    

    And for problem String to Integer (atoi) , here is my solution.

    public class Solution {
        public int myAtoi(String str) {
            str = str.replaceAll("^ *", "");
            if(str.length() == 0) return 0;
            System.out.println(str);
            boolean negative = false;
            int start = 0, end = -1;
            if(str.charAt(0) == '+' || str.charAt(0) == '-') {
                negative = str.charAt(0) == '-';
                start = 1;
            }
            for(end = start; end < str.length(); ++end)
                if(!Character.isDigit(str.charAt(end))) break;
            str = str.substring(start, end);
            System.out.println(str);
    
            try {
                if(str.length() == 0) return 0;
                return Integer.parseInt((negative ? "-" : "") + str);
            } catch(Exception e) {
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
        }
    }
    

    Both soluton got TLE at last case, but run code tells me the actual time is only about 40ms.

    The real solution use follow method to define p.
    int [] p = new int [n];


Log in to reply
 

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