FastPrep
Problem · String

Expression Add Operators

Learn this problem
● HardPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

Given a string digits containing only decimal digits and an integer target, insert the binary operators +, -, or * between some adjacent digits so that the resulting arithmetic expression evaluates to target.

  • You may concatenate adjacent digits to form a multi-digit operand.
  • An operand may be 0, but a multi-digit operand must not start with 0.
  • Use ordinary multiplication precedence: multiplication is evaluated before addition and subtraction.
  • Every digit must appear exactly once and in its original order.

Return every valid expression in ascending lexicographic order. Do not include duplicate expressions.

Function

addOperators(digits: String, target: int) → String[]

Examples

Example 1

digits = "123"target = 6return = ["1*2*3","1+2+3"]

Both 1 * 2 * 3 and 1 + 2 + 3 evaluate to 6. The returned strings are sorted lexicographically.

Example 2

digits = "105"target = 5return = ["1*0+5","10-5"]

The valid expressions are 1 * 0 + 5 and 10 - 5. An expression such as 1 * 05 is invalid because 05 has a leading zero.

Example 3

digits = "3456237490"target = 9191return = []

No permitted placement of the three operators produces the target.

Constraints

  • 1 <= digits.length <= 10
  • digits contains only characters from 0 through 9.
  • -2^31 <= target <= 2^31 - 1
  • Intermediate arithmetic fits in a signed 64-bit integer for all explored operands and expression values under these bounds.

More Pinterest problems

drafts saved locally
public String[] addOperators(String digits, int target) {
    // Write your code here.
}
digits"123"
target6
expected["1*2*3", "1+2+3"]
checking account