Time Limit Exceeded


  • 0
    X
        class Solution {
    public:
    
    bool headEqualTail(string s){
        if (s.length() == 0){
            return "";
        }
        int len = int(s.length());
        if(s[0] == s[len - 1]){
            return true;
        }
        else
            return false;
    }
    
    string evenLongestSubStr(string s){
        int curMaxLen = 0;
        int i,j;
        string maxSubStr = "";
        int len = s.length();
        if (len == 1){
            maxSubStr = maxSubStr + s[0];
            return maxSubStr;
        }
        for (i = 0 ; i < len - 1 ; i++ ){
            if(s[i] == s [i + 1]){
                string subStr(2,s[i]);
                for (j = i - 1 ; j >=0 && 2*i - j + 1<len ;j--){
                    string testStr = s[j] + subStr + s[2*i - j + 1];
                    if(headEqualTail(testStr)){
                        subStr = s[j] + subStr + s[2*i - j + 1];
                    }
                    else break;
                }
                if(subStr.length()>curMaxLen){
                    curMaxLen = int(subStr.length());
                    maxSubStr = subStr;
                }
            }
        }
        return maxSubStr;
    }
    
    string oddLongestSubStr(string s){
        int curMaxLen = 0;
        int i,j;
        string maxSubStr = "";
        int len = s.length();
        for (i = 0 ; i < len ;i++){
            string subStr (1,s[i]);
            for (j = i - 1; j >= 0 && 2*i - j<len ; j--){
                string testStr = s[j] + subStr + s[2*i - j];
                if(headEqualTail(testStr)){
                    subStr = s[j] + subStr + s[2*i-j];
                }
                else break;
            }
            if(subStr.length()>curMaxLen){
                curMaxLen = subStr.length();
                maxSubStr = subStr;
            }
        }
        return maxSubStr;
    }
    
    string longestPalindrome(string s) {
        string strEven = evenLongestSubStr(s);
        string strOdd = oddLongestSubStr(s);
        if(strEven.length()>strOdd.length()){
            return strEven;
        }
        else
            return strOdd;
    }
    
      
    };
    

    I run the code well on my own machine when using the input "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc". And when I choose this as custom testcase and run code I can also get the right answer in about 400ms. But when I submit It just tells me "Time Limit Exceeded". My basic idea is for every character in string expand both side and check if this string is palindromic . Can anyone tell my why this happen?


  • 0
    S

    The solution doesnt accept o(n^3) complexity!

    the bug bit me too :)


  • 0
    O

    My (accepted) solution executed your test case in 17ms and all 88 acceptance test cases in 50ms. https://leetcode.com/submissions/detail/43571573/
    https://docs.google.com/document/d/1awLKuNiSLoJSsprFhDk3jJwL5clooWBn-oNHwhPDccA/edit?usp=sharing


  • 0
    X

    The URL address you gave doesn't work for me, Are you sure this is the correct address?


  • 0
    O

    I've added link to a Google Doc that contains the code.


Log in to reply
 

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