TLE for O(n) code


#1

I followed codeschool and geeks solution and typed down here, still it is having TLE!


#2

I am facing same problem … not sure why its not working


#3
string Solution::solve(string A){
    int n = A.size();
    unordered_map<char, int> M;
    M['('] = 1;
    M['+'] = 2;
    M['-'] = 2;
    M['*'] = 3;
    M['/'] = 3;
    M['^'] = 4;
    vector<char> stack;
    string ans = "";
    for(int i = 0; i < n; i++){
        if(A[i] == '('){
            stack.push_back(A[i]);
            continue;
        }
        if(A[i] == ')'){
            while(stack.back() != '('){
                ans.push_back(stack.back());
                stack.pop_back();
            }
            stack.pop_back();
            continue;
        }
        if(A[i] - 'a' >= 0 && A[i] - 'z' < 26){
            ans.push_back(A[i]);
            continue;
        }
        while(!stack.empty() && M[stack.back()] >= M[A[i]]){
            ans.push_back(stack.back());
            stack.pop_back();
        }
        stack.push_back(A[i]);
    }
    while(!stack.empty()){
        ans.push_back(stack.back());
        stack.pop_back();
    }
    return ans;
}

Hope it Helps


#4

You may have concataneted the strings instead of pushing back. This can cause TLE if string is large


#5

push_back() also caused TLE!


#6

Same issue. I did in java