Given a number X, and a list of numbers lon = [N1, N2, ..., Nk], and a target number
F(X, lon, target) returns the combinations of "X * N1N2N3" that yields target, where the rules for inserting operator between digits is the same as problem described above
The only difference being there is a multiplication operator inserted after X already.
Our original problem asks for all possible arrangements of input lon such that each arrangement E satisfies Eval(E) = target. Well, by property 4, that is just a special case of the more generalized F, namely, F(1, lon, target).
We will show how to recursively apply F to compute the desired output. We do this by enumerating all cases based on the input.
Note: We denote lon as [N1, N2, ..., Nk]. Thus len(lon) = k
Base case
When k == 1, by definition of F, if X * N1 == target, this arrangement is qualified, and we return its string representation: str(X) + '*' + str(N1)
Recursive cases
Remember we can either insert one of the three operators, or not insert anything. Thus we have 4 cases:
Insert nothing
We keep N1 and N2 together in this case, but this only works if N1 is not '0', since something like '07' will not be a valid NumberString.
Assume that, and by definition of F, we can recursively compute the output as
F(X, [N1 * 10 + N2, N3, ..., Nk], target)
Insert +
The final arrangement will look like 'X * N1 + E', where E is whatever arrangement the rest of the lon ([N2, N3, ..., Nk]) came out to be.
Thus, we want this string to evaluate to target, meaning that,
Eval('X * N1' + '+' + E) = target. By property 1 we have:
target = Eval('X * N1') + Eval(E) = X * N1 + Eval(E)
In other words, we want Eval(E) = target - X * N1
What are the possible arrangements for that? That is precisely a subproblem to the original problem, thus the answer for that is
F(1, [N2, N3, ..., Nk], target - X * N1
Insert -
This is similar to the case with '+' above, because we can use property 2 to transform '-'.
We want Eval('X * N1' + '-' + E) = target. By property 2 we have:
target = Eval('X * N1') + Eval('-1*' + E) = X * N1 + Eval('-1*' + E)
In other words, we want Eval('-1*' + E) = target - X * N1
To solve this subproblem, we need to utilize the definition for F, which suggests that the answer is
F(-1, [N2, N3, ..., Nk], target - X * N1
Insert *
This follows the same pattern as the above cases.
We want Eval('X * N1' + '*' + E) = target. By property 3 we have:
target = Eval(str(Eval('X * N1')) + '*' + E)
By definition of F, we can derived the answer easily:
F(X * N1, [N2, N3, ..., Nk], target
|
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
lon = list(map(int, num))
answer = []
# F is exactly like what we defined above, except it has
# an extra argument to keep track of the partial string arrangement (including 'X*')
# already determined as it recurs down the search
# Also lon is represented as lon[start:]
# Viable arrangement will be appened into @answer in string form
def F(x, start, targ, prevArrangement):
# notice that start increments on every recursive call, so termination is ensured.
if start == len(lon) - 1:
if x * lon[start] == targ:
answer.append(prevArrangement + str(lon[start]))
return
# case 1 (no operator insertion)
# we have to modify the value of lon[start + 1]
# so we restore its value after the function returns
if lon[start] != 0:
lon[start + 1] += lon[start] * 10
F(x, start + 1, targ, prevArrangement)
lon[start + 1] -= lon[start] * 10
# case 2, insert '+'
F(1, start + 1, targ - x*lon[start], prevArrangement + str(lon[start]) + '+')
# case 3, insert '-'
F(-1, start + 1, targ - x*lon[start], prevArrangement + str(lon[start]) + '-')
# case 4, insert '*'
F(x * lon[start], start + 1, targ, prevArrangement + str(lon[start]) + '*')
# since we don't want to keep the "1*" in the front, we initialize
# prevArrangement to be empty string.
F(1, 0, target, "")
return answer
|
eg : ans = Solution()
num = "123", target = 6
ans.addOperators(nums, target)
Output -
["1+2+3", "1*2*3"]
| 
| 
