Build an Expression That Reaches a Target
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Build an Expression That Reaches a Target
Given a sequence of integers and a target, insert `+`, `-`, or `*` between adjacent numbers and add parentheses so that the resulting expression equals the target. Use every input number exactly once and preserve their original order.
Return the lexicographically smallest valid fully parenthesized expression under the grammar below, or an empty string if none exists. This canonical rule makes the output deterministic when several expressions reach the target.
### Function Signature
```python
def build_target_expression(numbers: list[int], target: int) -> str:
...
```
### Constraints
- `1 <= len(numbers) <= 9`
- `0 <= numbers[i] <= 100`
- `-10**9 <= target <= 10**9`
- Only binary `+`, `-`, and `*` may be used.
- Unary operators and concatenating adjacent numbers are not allowed.
- Every intermediate and final value fits in a signed 64-bit integer.
### Canonical Expression Grammar
- A one-number interval is rendered as that number's ordinary decimal string.
- Combining a left expression `L`, an operator `op`, and a right expression `R` is rendered exactly as `"(" + L + op + R + ")"`, with no spaces.
- Among all valid rendered expressions whose value is `target`, return the lexicographically smallest string using ordinary character ordering.
### Examples
```text
Input: numbers = [2, 3, 4], target = 14
Output: "(2*(3+4))"
Input: numbers = [2, 3, 4], target = 20
Output: "((2+3)*4)"
Input: numbers = [1, 1, 1], target = 10
Output: ""
```
### Clarifications
- Different parenthesizations are distinct possibilities because subtraction is not associative.
- You may discover many valid expressions internally, but the returned string must follow the canonical minimum rule.
- The generalized `n`-number version is the required version; three numbers are simply the smallest nontrivial case.
Quick Answer: Insert addition, subtraction, multiplication, and parentheses between numbers kept in their original order to reach a target. Use every input exactly once and return the lexicographically smallest fully parenthesized valid expression, or an empty string when none exists.
Using every input number exactly once in its original order, insert binary +, -, or * operations and parentheses to reach a target. Return the lexicographically smallest fully parenthesized valid expression, or an empty string when none exists.
Constraints
- There are between one and nine input numbers.
- Number order must be preserved and concatenation is forbidden.
- Only binary +, -, and * are allowed.
- Rendering contains no spaces and fully parenthesizes each binary operation.
- Return the lexicographically smallest valid rendering.
Examples
Input: ([2, 3, 4], 14)
Expected Output: '(2*(3+4))'
Explanation: The prompt expression reaches fourteen.
Input: ([2, 3, 4], 20)
Expected Output: '((2+3)*4)'
Explanation: The alternate prompt target needs a different parenthesization.
Hints
- Use interval dynamic programming.
- For each interval, map each reachable value to its smallest expression.
- Try every split and combine all reachable left and right values with each operator.