A O(n^2) solution in java passed the oj, but got "Time Limit Exceeded" in C++


  • 0
    W

    Java Implementation:

    public class Solution
    {
    public String longestPalindrome(String s)
    {
    if (s==null) return null;

        int n = s.length();
        if (n<2) return s;
        
        int start = 0;
        int end = 0;
        
        boolean[][] M = new boolean[n][n]; // all intialized to false, by default
        M[n-1][n-1] = true;
        for (int i=0; i<n-1; ++i) 
        {
            M[i][i] = true;
            M[i][i+1] = (s.charAt(i)==s.charAt(i+1));
            
            if (M[i][i+1])
            {
                start = i;
                end = i+1;
            }
        }
                
        for (int step=2; step<n; ++step)
        {
            for (int i=0; i<=n-1-step; ++i)
            {
                M[i][i+step] = M[i+1][i+step-1] && s.charAt(i)==s.charAt(i+step);
                if (M[i][i+step])
                {
                    start = i;
                    end = i+step;
                }
            }
        }
        
        return s.substring(start, end+1);
    }
    

    }

    =======================================

    C++ implementation:

    string longestPalindrome(string s) {
        int i, j, n, maxLen = 0;
        n = s.length();
        if (n <= 1) return s;
        
        vector<vector<bool> > P(n, vector<bool>(n, false));
        
        const char * ptr = s.data();
        for (i = 0; i < n; i++){
            P[i][i] = true;
        }
    
        string retval;
        for (i = 0; i < n-1; i++){
            P[i][i+1] = (ptr[i] == ptr[i+1]);
            if (P[i][i+1]){
                retval = s.substr(i, 2);
            }
        }
        
        for (i = 2; i < n; i++){
            for (j = 0; j < n-i; j++){
                P[j][j+i] = P[j+1][j+i-1] && (ptr[j] == ptr[j+i]);
    
                if (P[j][j+i] && maxLen < i){
                    maxLen = i;
                    retval = s.substr(j, i);
                }
            }
        }
        
        return retval;
    }

  • 3
    P
    1. Don't call substr() everytime you find a better result

    2. Don't use vector of vector, use static array instead.


    class Solution {
    public:
        string longestPalindrome(string s) {
            int i, j, n, maxLen = 0;
            n = s.length();
            if (n <= 1) return s;
    
            bool P[1001][1001];
            const char * ptr = s.data();
            for (i = 0; i < n; i++){
                P[i][i] = true;
            }
    
            string retval;
            int st,le;
            for (i = 0; i < n-1; i++){
                P[i][i+1] = (ptr[i] == ptr[i+1]);
                if (P[i][i+1]){
                    st = i;
                    le = 2;
                }
            }
    
            for (i = 2; i < n; i++){
                for (j = 0; j < n-i; j++){
                    P[j][j+i] = P[j+1][j+i-1] && (ptr[j] == ptr[j+i]);
    
                    if (P[j][j+i] && maxLen < i+1){ // Should be i + 1
                        maxLen = i+1; // Should be i + 1
                        st = j;
                        le = i+1; // Should be i + 1
                    }
                }
            }
            return s.substr(st,le);
        }
    };

  • 0
    W
    This post is deleted!

  • 0
    N
    This post is deleted!

  • 0
    X

    I have got the same confusion,I change the vector to static array and fortunately I get an accept,but I don't know the reason.


Log in to reply
 

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