Can you tell me why my C++ iterator method is not time efficient


  • 0
    S

    Hello,

    I have implemented a C++ solution using iterators. It runs out of time on the super long input

    "aaaaaaaaaaaaaaa....."

    My code is

    class Solution {
    public:
    string shortestPalindrome(string s) {
        if(s.size()<2)
            return s;
        string::iterator itback,itcent,itforw;
        itforw = s.begin();
        itlast = s.end()-1;
        while(true)
        {
            itback = itlast--;
            while(*(itforw)==*(itback))
            {
                if(itforw==itback || itforw+1==itback)
                {
                    string nonpal = s.substr(itlast+2-s.begin(),s.size()-(itlast+1-s.begin()));
                    reverse(nonpal.begin(),nonpal.end());
                    return nonpal+s;
                }
                itforw++; itback--;
            }
            itforw=s.begin();
        }
    }
    };
    

    Could you tell me why it is not time efficient ( whereas in this case it should see in N/2 operations that it is already a palindrome )
    Thanks for your help


  • 0

    Hi, This kind of method needs to consider implementation. In order to check if a substring is palindrome, you should start from middle. If you start from the two ends, you will get TLE because most of the checking would fail.


Log in to reply
 

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