Why is this java solution timing out?


  • 0
    A
    class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            boolean [][] arr = new boolean[len][len];
            int max = 1;
            int begin = 0;
            int end = 0;
            for(int i = len - 1; i >= 0; --i){
                for(int j = 0; j < len; ++j){
                    if(i == j) arr[i][j] = true;
                    else if(i + 1 < len && j - 1 >= 0 && j - i + 1 > 2){
                        arr[i][j] = arr[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                        if(newMax(max, i, j, arr[i][j])){max = j - i + 1; begin = i; end = j;}
                    }
                    else if (i + 1 < len && j - 1 >= 0){
                        arr[i][j] = (s.charAt(i) == s.charAt(j));
                        if(newMax(max, i, j, arr[i][j])){max = j - i + 1; begin = i; end = j;}
                    } 
                }
            }
            
            return s.substring(begin, end + 1);
        }
        
        private boolean newMax(int oldMax, int newI, int newJ, boolean cell){
            return (cell && (newJ - newI + 1 > oldMax));
        }
    }
    

    I have no clue why it fails the last time (times out). I'm only generating 1 substring, so it should really be O(N^2). Any idea?


Log in to reply
 

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