Insert Operators to Reach a Target
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Insert Operators to Reach a Target
Implement `expressions_for_target(digits: str, target: int) -> list[str]`.
Insert zero or more binary operators `+`, `-`, or `*` between the digits, without reordering them, so that each resulting expression evaluates to `target`. Return every valid expression.
### Input Domain
- `1 <= len(digits) <= 10`.
- `digits` contains only characters `0` through `9`.
- `target` fits in a signed 32-bit integer.
- Every intermediate arithmetic value fits in a signed 64-bit integer.
### Output Rules
- Return all valid expressions in ascending lexicographic order.
- An operand may contain several digits, but it may not have a leading zero unless the operand is exactly `0`.
- Use ordinary arithmetic precedence: multiplication binds more tightly than addition or subtraction.
- Do not include parentheses, unary operators, duplicates, or whitespace.
### Constraints
- The empty result is valid when no expression reaches the target.
- Ordering is part of the expected output and resolves all multiple-answer ambiguity.
### Examples
#### Example 1
Input: `digits = "123", target = 6`
Output: `["1*2*3","1+2+3"]`
#### Example 2
Input: `digits = "105", target = 5`
Output: `["1*0+5","10-5"]`
```hint Track the most recent term
To append multiplication without reparsing the whole expression, retain both the accumulated value and the signed value of the last multiplicative term.
```
Quick Answer: Generate every lexicographically ordered expression formed by inserting arithmetic operators that evaluates to a target value.
Given a string of digits, insert zero or more binary operators +, -, or * between digits without reordering them, and return every expression that evaluates to target. Operands may contain several digits but may not have a leading zero unless the operand is exactly 0. Use ordinary arithmetic precedence, with multiplication binding more tightly than addition or subtraction. Return no parentheses, unary operators, duplicates, or whitespace, and sort all valid expressions in ascending lexicographic order.
Constraints
- 1 <= len(digits) <= 10.
- digits contains only characters 0 through 9.
- target fits in a signed 32-bit integer, and every intermediate arithmetic value fits in a signed 64-bit integer.
- Operands preserve digit order and cannot have a leading zero unless the operand is exactly 0.
- Only binary +, -, and * are allowed, with ordinary multiplication precedence; do not use parentheses, unary operators, duplicates, or whitespace.
- Return every valid expression in ascending lexicographic order; an empty list is valid when none reaches target.
Examples
Input: ('0', 0)
Expected Output: ['0']
Explanation: A single zero is a valid one-digit operand.
Input: ('7', 8)
Expected Output: []
Explanation: A single unmatched digit has no valid expression.
Hints
- Build each operand from a consecutive slice, and treat a zero at the start of a slice as a boundary.
- Keep enough information about the most recent term to append multiplication without reparsing the expression.