problem282

package
v1.6.6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 27, 2021 License: MIT Imports: 0 Imported by: 0

README

< Previous                  Next >

282. Expression Add Operators (Hard)

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

 

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Explanation: Both "1*0+5" and "10-5" evaluate to 5.
Note that "1-05" is not a valid expression because the 5 has a leading zero.

Example 4:

Input: num = "00", target = 0
Output: ["0*0","0+0","0-0"]
Explanation: "0*0", "0+0", and "0-0" all evaluate to 0.
Note that "00" is not a valid expression because the 0 has a leading zero.

Example 5:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

 

Constraints:

  • 1 <= num.length <= 10
  • num consists of only digits.
  • -231 <= target <= 231 - 1

[Math] [String] [Backtracking]

Similar Questions

  1. Evaluate Reverse Polish Notation (Medium)
  2. Basic Calculator (Hard)
  3. Basic Calculator II (Medium)
  4. Different Ways to Add Parentheses (Medium)
  5. Target Sum (Medium)

Hints

Hint 1 Note that a number can contain multiple digits.
Hint 2 Since the question asks us to find all of the valid expressions, we need a way to iterate over all of them. (Hint: Recursion!)
Hint 3 We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion?
Hint 4 Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators.


1 + 2 = 3
1 + 2 - 4 --> 3 - 4 --> -1
1 + 2 - 4 * 12 --> -1 * 12 --> -12 (WRONG!)
1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!)

Hint 5 We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator.

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL