My C++ solution got "output limit exceeded", but the output is same in the test


  • 0
    R

    So I am using the backtracking methods to read each number. So I keep updating the eqation a+bc, where c is the current number, a is the previous summation results, b is the previous product results. For each round, the number c is readed, and there are three choices after c: '+', '-', ''.

    For '+', new_a = a+bc, and new_b = 1;
    For '-', new_a = a+b
    c, and new_b = -1;
    For'', new_a= a, and new_b = bc;

    So my c++ code is pasted as below:

    class Solution {
    public:
        int s2i(string s)
        {
            int i;
            int siz = s.size();
            int res = 0;
            for(i=0; i<siz; i++) res = 10*res + (int)(s[i]-'0');
            return res;
        }
        void dfs(vector<string> & res, string & temp, string num, int target, int a, int b)
        {
            int temp_siz = temp.size();
            int siz = num.size();
            string tmp1, tmp2;
            int a_tmp, b_tmp;
            int i;
            if((num[0] != '0' && (a+b*s2i(num)) == target) || (siz == 1 && num[0] == '0')) 
            {
                temp+=num;
                res.push_back(temp);
                temp.erase(temp.begin()+temp_siz, temp.end());;
                return;
            }
            else
            {
                for(i=0; i<siz-1; i++)
                {
                    tmp1 = num.substr(0, i+1);
                    tmp2 = num.substr(i+1, siz-i-1);
                    b_tmp = b*s2i(tmp1);
                    // if next sign is *
                    temp+=(tmp1+"*");
                    dfs(res, temp, tmp2, target, a, b_tmp);
                    temp.erase(temp.begin()+temp_siz, temp.end());
                    // if next sign is +
                    temp+=(tmp1+"+");
                    dfs(res, temp, tmp2, target, a+b_tmp, 1);
                    temp.erase(temp.begin()+temp_siz, temp.end());
                    // if nex sign is -
                    temp+=(tmp1+"-");
                    dfs(res, temp, tmp2, target, a+b_tmp, -1);
                    temp.erase(temp.begin()+temp_siz, temp.end());
                    
                    if(i == 0 && num[i] == '0') break;
                }
                return;
            }
        }
        vector<string> addOperators(string num, int target) {
            vector<string> res;
            string temp;
            int a = 0;
            int b = 1;
            dfs(res, temp, num, target, a, b);
            return res;
        }
    };
    

    My solution is not accepted. In the test case of "123456789", 45. It gets the problem of "output limit exceeded". I just pasted the test case into the run session, and compared it with the expected results. It is same. I am wondering what is wrong with my solution. Thanks very much.


  • 0
    H

    I follow same idea as you but code is different. I also see same error in some runs.

    Be careful:
    1, use long int.
    2, if current position is already end of string, do not attempt 3 operators.
    3, if current char is 0, it can be only used once, you can not have a number like 05.
    4, when you exit each dfs(), you need to make sure the "string temp" in your code is intact.


Log in to reply
 

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