796. Expression Add Operators — Count Expressions Reaching Target

Given a string num containing only digits and an integer target, return the NUMBER of distinct ways to insert the binary operators '+', '-', and '*' between the digits of num so that the resulting expression evaluates to target. Operands in the expression MUST NOT have leading zeros (e.g., '05' is not valid, but '0' alone is). Standard operator precedence applies (* before +/-). Input is a JSON object with fields num (string) and target (int).

Input: A JSON object: {"num":"digits","target":T}.

Output: Return an integer count.

Examples

Input: {"num":"123","target":6}
Output: 2
Explanation: 1+2+3=6 and 1*2*3=6.

Input: {"num":"232","target":8}
Output: 2
Explanation: 2+3*2=8 and 2*3+2=8.

Input: {"num":"00","target":0}
Output: 3
Explanation: 0+0, 0-0, 0*0 all equal 0.

Constraints

• 1 <= num.length <= 8
• num consists of digits '0'..'9'
• -2^31 <= target <= 2^31 - 1

Asked by