Same dp code, c++ passes while python got TLE. HELP


  • 5

    Python version

    class Solution:
    # @param s, a string
    # @return a string
    def longestPalindrome(self, s):
        st = 0
        maxl = 0
        dp = [[False]*1000 for i in xrange(1000)]
        for i in reversed(xrange(len(s))):
            for j in xrange(i,len(s)):
                if s[i] == s[j] and (i+1>j-1 or dp[i+1][j-1] ):
                    dp[i][j] = True
                    if j-i+1 > maxl:
                        st = i
                        maxl = j-i+1
    
        return s[st:st+maxl]
    

    C++ version

    class Solution {
    public:
    string longestPalindrome(string s) {
        int start = 0, maxLen = 1, n = s.size();
        bool isPal[1000][1000] = {false};
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j]) {
                    isPal[i][j] = true;
                    if(j-i+1>maxLen) {
                        maxLen = j-i+1;
                        start = i;
                    }
                }
            }
        }
        return s.substr(start,maxLen);
    }
    

    };

    I have spent hours on this, any help would be appreciated.
    I know for sure reversed() method won't make copy
    So what causes python version TLE


  • 0
    D

    same here on python, exactly same java code can pass.


  • 0

    so do I. I got the same issue in Javascript.


  • 0
    A

    I use the same solution and get TLE as well... Help


  • 0

    I have just fixed this. Now the same Python code can pass.


Log in to reply
 

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