Practice/LinkedIn/Leetcode 282. Expression Add Operators

Leetcode 282. Expression Add Operators

CodingMust

Problem

You are given a string containing only digits and an integer target value. Your task is to insert the binary operators +, -, and * between the digits to create valid mathematical expressions that evaluate to the target value. Return all possible expressions that evaluate to the target.

You can form multi-digit numbers by not placing an operator between consecutive digits. However, you must not create numbers with leading zeros (e.g., "05" is invalid, but "0" alone is valid).

The operators follow standard mathematical precedence where multiplication is evaluated before addition and subtraction.

Requirements

1. Return all valid expressions as strings that evaluate to the target
2. Expressions should contain the original digits in their original order
3. Do not create operands with leading zeros (except the number 0 itself)
4. Handle operator precedence correctly (multiplication before addition/subtraction)
5. Return an empty list if no valid expressions exist

Constraints

• 1 ≤ num.length ≤ 10
• num consists of only digits
• -2³¹ ≤ target ≤ 2³¹ - 1
• Time complexity should be reasonable for the input size

Examples

Example 1:

` Input: num = "123", target = 6 Output: ["1+2+3", "123"] Explanation:

• 1+2+3 = 6
• 123 = 6 Both expressions evaluate to the target value. `

Example 2:

` Input: num = "232", target = 8 Output: ["23+2", "2+32"] Explanation:

• 2*3+2 = 6+2 = 8
• 2+3*2 = 2+6 = 8 `

Example 3:

` Input: num = "105", target = 5 Output: ["1*0+5", "10-5"] Explanation:

• 1*0+5 = 0+5 = 5
• 10-5 = 5 Note that "1-05" is invalid due to leading zero in "05". `

Example 4:

Input: num = "00", target = 0 Output: ["0+0", "0-0", "0*0"] Explanation: All three expressions evaluate to 0.