Why is my O(n^2) soltuion giving a time limit exceeded error?


  • 0
    N
    int isPal(string &s,int n){
    n++;
    for(int i = 0; i < n/2; i++){
        if(s[i] != s[n-i-1]) return 0;
    }
    return 1;
    

    }

    class Solution {
    public:
    string shortestPalindrome(string s) {
    int n = s.size();
    int nw = 0;
    for(int i = n-1; i >= 0; i--){
    if(isPal(s,i))
    {
    nw = n - (i+1);
    break;
    }
    }
    string r = s.substr(n-1 - (nw -1),nw);
    reverse(r.begin(),r.end());
    return r+s;
    }
    };


Log in to reply
 

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