Why getting a wrong answer when input is "abb"?


  • 1
    H

    My ALG runs correctly in local but get a wrong answer here for "abb".

    Could someone tell me why?

    string longestPalindrome(string s) {
        if(s == ""){
            return "";
        }
        string sT = "";
        //get the transpose of s
        for(int i = s.length(); i>0; i--){
            sT += s[i-1];
        }
        
        //construct dynamic table and initialize it
        int dp_table[1001][1001];
        for(int i = 0; i<s.length()+1; i++){
            dp_table[0][i] = 0;
            dp_table[i][0] = 0;
        }
        
        //finding the longest palindromic substring
        for(int i = 0; i<s.length(); i++){
            for(int j = 0; j<s.length(); j++){
                if(s[i] == sT[j]){
                    dp_table[i+1][j+1] = dp_table[i][j]+1;
                }
            }
        }
        int max = 0;
        int x;
        int y;
        for(int i = 0; i<s.length()+1; i++){
            for(int j = 0; j<s.length()+1; j++){
                if(max < dp_table[i][j]){
                    max = dp_table[i][j];
                    x = i;
                    y = j;
                }
            }
        }
        
        //reconstruct the substring
        string result = "";
        while(dp_table[x][y] != 0){
            result += s[x-1];
            x--;
            y--;
        }
        string result0 = "";
        for(int i = result.length(); i>0; i--){
            result0 += result[i-1];
        }
        return result0;
    }

  • 0
    Y
    if(s[i] == sT[j]){
        dp_table[i+1][j+1] = dp_table[i][j]+1;
    }
    

    Here you should add:

    else {
        dp_table[i+1][j+1] = 0;
    }

Log in to reply
 

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