my C++ code using dynamic programming


  • 0
    C

    There are two basic cases for starting DP.
    When length is odd, for example "xax",
    and when length is even, for example "xaax".

    bool D[1001][1001];
    
    class Solution {
    public:
        string longestPalindrome(string s) {
            int len = s.length();
                /* base case */
                for(int i=0; i<len; i++){
                    for(int j=0;j<len;j++)
                        D[i][j] = false;
                    D[i][i] = true;
                }
    
                int max = 1;
                int start = 0;
                int end = 0;
    
                /* base case for even length */
                for(int i=0; i<len; i++){
                    if(i+1 < len){
                        D[i][i+1] = s.at(i) == s.at(i+1) ? true: false;
                        if(D[i][i+1]){
                            max = 2;
                            start = i;
                            end = i+1;
                        }
                    }
                }
    
                int s_i, e_i;
                for(int i=0; i< len; i++){
                    /* odd */
                    s_i=i-1;
                    e_i=i+1;
                    while(s_i>=0 && e_i<=len-1){
                        if(D[(s_i+1)][e_i-1] && (s.at(s_i) == s.at(e_i))){
                            D[s_i][e_i] = true;
                            /* update max */
                            if((e_i-s_i+1) > max){
                                max = e_i-s_i+1;
                                start = s_i;
                                end = e_i;
                            }
                        }
                        s_i--;
                        e_i++;
                    }
                    /* even */
                    s_i=i-1;
                    e_i=i+2;
                    while(s_i>=0 && e_i<=len-1){
                        if(D[(s_i+1)][e_i-1] && (s.at(s_i) == s.at(e_i))){
                            D[s_i][e_i] = true;
                            /* update max */
                            if((e_i-s_i+1) > max){
                                max = e_i-s_i+1;
                                start = s_i;
                                end = e_i;
                            }
                        }
                        s_i--;
                        e_i++;
                    }
                }
           
                return s.substr(start, max);
            }
    };
    

Log in to reply
 

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