Disparity of TLE based on languages.


  • 0

    I tried to follow this solution (https://discuss.leetcode.com/topic/41047/o-n-using-idea-similar-to-lps-358-msec/2) in C++.
    His original JAVA solution passes in ~358 ms (as claimed). Contrary to what's written in the title, the solution runs in no less than O(n**2). I have taken note of that.
    Replicating this in C++ 1 takes up 1480 ms for one large test case alone (the one with "aaaaaa....cd......aaaa") and obviously times out when submitted.

    This is an obvious disparity over run time costs in different languages for a test case. I know that much faster solutions exist for this problem. But the fact that a slow approach is accepted in one language and not in another is unsettling. Any suggestions on how to fix this?

    This issue not entirely isolated. Another O(n**2) solution (https://discuss.leetcode.com/topic/47699/accepted-c-solution-easy-to-understand) seems to be accepted.


    1 The rogue code looks like this:

    class Solution {
    public:
        string shortestPalindrome(string s) {
            int mid = s.length()/2, n = s.length();
            string pre;
            pair<int, int> ret;
          
            for(int i=mid-1; i>=0; i--) {
                // even length
                ret = expandString(s, i, i+1);
                if(ret.first == -1) {
                    pre = s.substr(ret.second);
                    reverse(pre.begin(), pre.end());
                    return pre + s;
                }
                
                // odd length
                ret = expandString(s, i, i);
                if(ret.first == -1) {
                    pre = s.substr(ret.second);
                    reverse(pre.begin(), pre.end());
                    return pre + s;
                }
            }
            
            return "";
        }
        
        pair<int, int> expandString(string &s, int left, int right) {
            while(left >= 0 && right < s.length() && (s[left] == s[right])) {
                left--;
                right++;
            }
            return make_pair(left, right);
        }
    };
    

Log in to reply
 

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