Accepted C++ Solution


  • 25
    J
    void addOperators(vector<string>& result, string nums, string t, long long last, long long curVal, int target) {
    	if (nums.length() == 0) {
    		if (curVal == target)
    			result.push_back(t);
    		return;
    	}
    
    	for (int i = 1; i<=nums.length(); i++) {
    		string num = nums.substr(0, i);
    		if(num.length() > 1 && num[0] == '0')
    		    return;
    		
    		string nextNum = nums.substr(i);
    
    		if (t.length() > 0) {
    			addOperators(result, nextNum, t + "+" + num, stoll(num), curVal + stoll(num), target);
    			addOperators(result, nextNum, t + "-" + num, -stoll(num), curVal - stoll(num), target);
    			addOperators(result, nextNum, t + "*" + num, last * stoll(num), (curVal - last) + (last * stoll(num)), target);
    		}
    		else 
    			addOperators(result, nextNum, num, stoll(num), stoll(num), target);
    	}
    }
    
    vector<string> addOperators(string num, int target) {
    	vector<string> result;
    	addOperators(result, num, "", 0, 0, target);
    	return result;
    }

  • 0
    A

    Clear Approach.
    I wrote in Java according to your solution.

    public List<String> addOperators(String num, int target) {
    List<String> result = new ArrayList<String>();
    helper(result, num, "", 0, 0, target);
    return result;
    }

    public void helper(List<String> result, String num, String cur, long last, long curVal, int target) {
        if (num.length() == 0) { //used up right part of string num
            if (curVal == target) {
                result.add(cur);
            }
            
            return;
        }
        
        for (int i = 1; i <= num.length(); i++) {
            String left = num.substring(0, i);
            if (left.length() > 1 && left.charAt(0) == '0') {
                return; ///invalid case: 01..
            }
            String right = num.substring(i);
            if (cur.length() > 0) {
                helper(result, right, cur + "+" + left, Long.valueOf(left), curVal + Long.valueOf(left), target);
                helper(result, right, cur + "-" + left, -Long.valueOf(left), curVal - Long.valueOf(left), target);
                helper(result, right, cur + "*" + left, last * Long.valueOf(left), (curVal - last) + (last * Long.valueOf(left)), target);
            } else {
                helper(result, right, left, Long.valueOf(left), Long.valueOf(left), target);
            }
        }
    }

  • 0
    T

    My idea is quite simple. In each positon between two characters, there are 4 choices, i.e, we can post '+', '-','', ' ', so we can change this problem to quaternary system. But this idea is very likery to TLE. My code is here. Not AC.TLE
    #include<iostream>
    #include<cassert>
    #include<vector>
    #include<stack>
    #include<sstream>
    #include<string>
    using namespace std;
    string num2str(int x, int len, int base = 2)
    {
    string ret;
    while (x != 0)
    {
    ret += (x % base + '0');
    x /= base;
    }
    int len2append = len - ret.length();
    for (int i = 0; i < len2append; i++)
    ret += "0";
    reverse(ret.begin(), ret.end());
    return ret;
    }
    char ops[] = { ' ', '+', '-', '
    ' };//0 : space, 1: '+', 2: '-', 3: ''
    int compute(int x, int y, char op)
    {
    switch (op)
    {
    case '+':
    return x + y;
    case '-':
    return x - y;
    case '
    ':
    return xy;
    default:
    cout << "Wrong answer!" << endl;
    return -1;
    }
    }
    void eval(const string& expr, const string& mark, int tgt, vector<string>& result)
    {
    int ret = expr[0] - '0';
    int len = expr.length() - 1;
    assert(mark.length() == len);
    stack<int> st_num;
    char ch, t_ops;
    stack<char> st_ops;
    int r, l, t;
    for (int i = 0; i < len; i++)
    {
    if ((ch = ops[mark[i] - '0']) == ' ')
    ret = ret * 10 + expr[i + 1] - '0';
    else
    {
    st_num.push(ret);
    ret = expr[i + 1] - '0';
    if (st_ops.empty())
    st_ops.push(ch);
    else
    {
    switch (ch)
    {
    case '+':
    case '-':
    {
    r = st_num.top();
    st_num.pop();
    l = st_num.top();
    st_num.pop();
    t_ops = st_ops.top();
    t = compute(l, r, t_ops);
    st_num.push(t);
    st_ops.pop();
    st_ops.push(ch);
    break;
    }
    case '
    ':
    {
    if (st_ops.top() == ch)
    {
    r = st_num.top();
    st_num.pop();
    l = st_num.top();
    st_num.pop();
    t_ops = st_ops.top();
    t = l * r;
    st_num.push(t);
    }
    else
    st_ops.push(ch);
    }
    }
    }
    }
    }

    st_num.push(ret);
    while (!st_ops.empty())
    {
    	r = st_num.top();
    	st_num.pop();
    	l = st_num.top();
    	st_num.pop();
    	st_num.push(compute(l, r, st_ops.top()));
    	st_ops.pop();
    }
    if (st_num.top() == tgt)
    {
    	string tmp;
    	tmp += expr[0];
    	for (int i = 0; i < len; i++)
    	{
    		if (ops[mark[i] - '0'] == ' ')
    			tmp += expr[i + 1];
    		else
    		{
    			tmp += ops[mark[i] - '0'];
    			tmp += expr[i + 1];
    		}
    	}
    	if (tmp.length() != expr.length())
    		result.push_back(tmp);
    }
    

    }
    vector<string> addOperators(string num, int target)
    {
    vector<string> ret;
    int len = num.length();
    if (len <= 0)
    {
    return ret;
    }
    else if (len == 1)
    {
    if (num[0] - '0' == target)
    ret.push_back(num);
    return ret;
    }
    else
    {
    len--;
    long long x = 1;
    for (int i = 0; i < len; i++)
    x *= 4;
    for (int i = 0; i < x; i++)
    {
    string str = num2str(i, len, 4);
    eval(num, str, target, ret);
    }
    return ret;
    }
    }
    int main()
    {
    string num = "3456237490";
    vector<string> ret = addOperators(num, 9191);
    for (auto& e : ret)
    {
    cout << e << endl;
    }
    return 0;
    }


  • 0

    @tiandu Please post your comment as a separate answer instead. It's hard to read comments that contain code which is long. Could you please format your code properly?


  • 0
    C

    It would be better If you can explain the solution


  • 0

    Thank you for your nice solution, but could you tell me why string nextNum = nums.substr(i); can passed compilation when i==nums.length()?


  • 0

    What's more, I have run your code on my computer, when come to the case :

    s="3456237490", target=9191
    

    It looks like TLE, (I have waited for a while and result never be returned) =.=||.


  • 1
    J

    When "i==nums.length()", "nextNum" is empty. "nextNum" is used as "nums" at next recursive call. When "nums" is equal to empty, the function check if the curVal is eqaul to target.


  • 0
    J

    When it comes to your second question, I don't know the reason. It looks like there is no solution to the test case. When I run the code in my computer, it terminates in 3 second.


Log in to reply
 

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