Wrong answer on input "aaabaaaa" but works fine in Ideone


  • 0
    H

    I am trying to do this in O(n^2) with auxiliary space of O(n^2), which is bool table[1000][1000]. I find out the starting index and the maxLength of the longest Palindromic substring starting from substrings of length 2 to n. It gives correct output in Ideone (http://ideone.com/FqmmNU) and CodeBlocks, but here :
    Input: "aaabaaaa"
    Output: "aaabaaaa"
    Expected: "aaabaaa" .
    Please help.

    char* longestPalindrome(char* s) {
        int n = strlen(s) ; 
        if(n <= 1)
           return s ;
        int i, j, l ;
        bool table[1000][1000] ;
        for(i = 0 ; i < n ; i++)
           table[i][i] = true ;
        int start = 0, maxLength = 1 ;
        
        for(l = 2 ; l <= n ; l++) {
            for(i = 0 ; i < n-l+1 ; i++) {
                j = i+l-1 ;
                if(l == 2) {
                    if(s[i] == s[j]) {
                        table[i][j] = true ;
                        start = i ;
                        maxLength = 2 ;
                    }
                }
                else {
                    if(table[i+1][j-1] && (s[i] == s[j]) ) {
                        table[i][j] = true ;
                        if(l > maxLength) {
                            start = i ;
                            maxLength = l ;
                        }
                    }
                }
            }
        }
        char *pal = (char *)malloc((maxLength+1) * sizeof(char) ) ;
        for(i = start, j = 0 ; i <= start + maxLength - 1 ; i++, j++)
           pal[j] = s[i] ;
        pal[j] = '\0' ;
        return pal ;
    }

  • 2
    M

    You should initialize the array, maybe some compilers will do it for you , others will not. It's safe to do it yourself

    bool table[1000][1000] ;
    memset(table,false,sizeof(table));
    

    BTW, I think 'l' is not a good variable. It's difficult to tell 'l' from '1'.


  • 0
    H

    Thanks a lot for the answer.


Log in to reply
 

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