This solution is simple but timed out for a long "aaaaaaaaaa...........bc...aaaa" string?


  • 0
    C

    This solution is simple but time out for a long "aaaaaaaaaa...........bc...aaaa" string.

    class Solution {
    public:
        string longestPalindrome(string s) {
            
            string ret;
            map<int,int> ms;
            
            int sz=s.size();
            if(sz<=1) return s;
            if(sz==2)
            {
                if(s[0]==s[1]) return s;
                else return s.substr(0,1);
            }
            ms.insert(pair<int,int>(1,0));
            
            for(int i=0;i<sz;i++)   //search starts from the beginning
            {
                for(int j=sz-1;j>i;j--) //search range from the end then backwards
                {
                    if(p(s,i,j))
                    {
                        ms.insert(pair<int,int>(j-i+1,i));
                        break;  //once found, search starts from the next beginning
                    }
                }
            }
            
            map<int,int>::reverse_iterator it = ms.rbegin();
            return s.substr(it->second,it->first);
        }
            
          bool p(string s, int start, int end)
          {
              //is this range a palin?
              int sz=end-start+1;
              string sub=s.substr(start,sz);
              
              for(int i=0;i<sz/2;i++)
              {
                  if(sub[i]!=sub[sz-1-i])
                  return false;
              }  
              return true;
          }
    };

  • -2
    X

    use array not map or vector then accept


  • 0
    I

    I did the exact same thing, but with array and its still timing out for the string mentioned in the post.


  • 0
    K

    This is an O(n^3) algorithm, oj is looking for O(n^2)


Log in to reply
 

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