281. Expression Add Operators (Count)

Given a string num of digits and an integer target, return the number of distinct ways to insert the binary operators '+', '-', or '*' (or nothing) between the digits so that the resulting expression evaluates to target. Operands may not have leading zeros (except '0' itself). Input: '"num", target'.

Input: '"num", target'.

Output: Integer — number of valid expressions.

Examples

Input: "123", 6
Output: 2
Explanation: 1+2+3 and 1*2*3.

Input: "232", 8
Output: 2
Explanation: 2*3+2 and 2+3*2.

Input: "105", 5
Output: 2
Explanation: 1*0+5 and 10-5.

Constraints

• 1<=num.length<=10
• digits only
• -2^31<=target<=2^31-1

Asked by