Time Limit Exceeded for Longest Palindromic Substring


  • 0
    S

    It would be very helpful if anybody can point out the bug here.

    package longestPalindromicSubstr;

    public class Solution {
    private int table [] [];
    private int len;
    private static final int NOT_COMPUTED = -1;
    private static final int NOT_PALINDROME = 0;

    public String longestPalindrome(String s) {
    	int i = 0, j = 0;
    	len = s.length();
    	table = new int [s.length()][s.length()];
    	
    	for(i=0; i< len; i++) {
    		for(j = 0; j < len; j++) {
    			table[i][j] = NOT_COMPUTED;
    		}
    	}
    
    	//First fill the diagonals and adjacent to diagonals
    	for(i = 0; i < s.length(); i++) {
    		table[i][i] = 1;
    		if(i+1 < len) {
    			if(s.charAt(i) == s.charAt(i+1)) {
    				table[i][i+1] = 2;
    			}else {
    				table[i][i+1] = NOT_PALINDROME;
    			}
    		}
    	}
    
    	//Now fill other rows
    	for(i = 0; i < len; i++) {
    		for(j = 0; j < len; j++) {
    			if(j <= i+1)
    				continue;
    			if(s.charAt(i) == s.charAt(j) && table[i][j] == NOT_COMPUTED) {
    					compute(i, j);
    			}
    		}
    	}
    
    	return findLongestSubstr(s);
    }
    
    private void compute(int row, int col) {
    	if(col < row) {
    		System.out.println("Should not reach here");
    		System.exit(-1);
    	}
    	
    	if(table[row+1][col-1] == NOT_COMPUTED)
    		compute(row+1, col-1);
    	
    	if(table[row+1][col-1] == NOT_PALINDROME)
    		table[row][col] = NOT_PALINDROME;
    	else
    		table[row][col] = table[row+1][col-1] + 2;
    }
    
    private String findLongestSubstr(String s) {
    	int currMax = 0;
    	int maxRow = 0;
    	int maxCol = 0;
    
    	for(int i = 0; i < len ; i++) {
    		for(int j = 0; j < len; j++) {
    			if(j < i)
    				continue;
    			if(table[i][j] > currMax) {
    				currMax = table[i][j];
    				maxRow = i;
    				maxCol = j;
    			}
    		}
    	}
    	
    	return s.substring(maxRow, maxCol+1);
    }
    

    }


Log in to reply
 

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