题目大意:给你一个字符串,让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。
Given a string that contains only digits 0-9
and a target value, return all possibilities to add binary operators (not unary) +
, -
, or *
between the digits so they evaluate to the target value.
Examples:
1 2 3 4 5 |
"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> [] |
Slides:
Solution 1: DFS
Time complexity: O(4^n)
Space complexity: O(n^2) -> O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua // Running time: 128 ms (<79.97%) class Solution { public: vector<string> addOperators(string num, int target) { vector<string> ans; dfs(num, target, 0, "", 0, 0, &ans); return ans; } private: void dfs(const string& num, const int target, // input int pos, const string& exp, long prev, long curr, // state vector<string>* ans) { // output if (pos == num.length()) { if (curr == target) ans->push_back(exp); return; } for (int l = 1; l <= num.size() - pos; ++l) { string t = num.substr(pos, l); if (t[0] == '0' && t.length() > 1) break; // 0X... long n = std::stol(t); if (n > INT_MAX) break; if (pos == 0) { dfs(num, target, l, t, n, n, ans); continue; } dfs(num, target, pos + l, exp + '+' + t, n, curr + n, ans); dfs(num, target, pos + l, exp + '-' + t, -n, curr - n, ans); dfs(num, target, pos + l, exp + '*' + t, prev * n, curr - prev + prev * n, ans); } } }; |
C++ / SC O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua // Running time: 13 ms (< 99.14%) class Solution { public: vector<string> addOperators(string num, int target) { vector<string> ans; string exp(num.length() * 2, '\0'); dfs(num, target, 0, exp, 0, 0, 0, &ans); return ans; } private: void dfs(const string& num, const int target, int pos, string& exp, int len, long prev, long curr, vector<string>* ans) { if (pos == num.length()) { if (curr == target) ans->push_back(exp.substr(0, len)); return; } long n = 0; int s = pos; int l = len; if (s != 0) ++len; while (pos < num.size()) { n = n * 10 + (num[pos] - '0'); if (num[s] == '0' && pos - s > 0) break; // 0X... invalid number if (n > INT_MAX) break; // too long exp[len++] = num[pos++]; if (s == 0) { dfs(num, target, pos, exp, len, n, n, ans); continue; } exp[l] = '+'; dfs(num, target, pos, exp, len, n, curr + n, ans); exp[l] = '-'; dfs(num, target, pos, exp, len, -n, curr - n, ans); exp[l] = '*'; dfs(num, target, pos, exp, len, prev * n, curr - prev + prev * n, ans); } } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// Author: Huahua // Running time: 16 ms (<99.17%) class Solution { private List<String> ans; private char[] num; private char[] exp; private int target; public List<String> addOperators(String num, int target) { this.num = num.toCharArray(); this.ans = new ArrayList<>(); this.target = target; this.exp = new char[num.length() * 2]; dfs(0, 0, 0, 0); return ans; } private void dfs(int pos, int len, long prev, long curr) { if (pos == num.length) { if (curr == target) ans.add(new String(exp, 0, len)); return; } int s = pos; int l = len; if (s != 0) ++len; long n = 0; while (pos < num.length) { if (num[s] == '0' && pos - s > 0) break; // 0X... n = n * 10 + (int)(num[pos] - '0'); if (n > Integer.MAX_VALUE) break; // too long exp[len++] = num[pos++]; // copy exp if (s == 0) { dfs(pos, len, n, n); continue; } exp[l] = '+'; dfs(pos, len, n, curr + n); exp[l] = '-'; dfs(pos, len, -n, curr - n); exp[l] = '*'; dfs(pos, len, prev * n, curr - prev + prev * n); } } } |