Expression Add Operators
Intuition
Solution
class Solution:
def _helper(self, prefix, prev, diff, num):
if not num:
yield prefix, prev
return StopIteration
# TODO: num starts with zero
if not prefix:
for i in range(1, len(num) + 1):
start = num[:i]
if len(start) > 1 and start[0] == '0':
break
for s, v in self._helper(start, int(start), int(start), num[i:]):
yield s, v
return StopIteration
for i in range(1, len(num) + 1):
start = num[:i]
if len(start) > 1 and start[0] == '0':
break
for s, v in self._helper(prefix + '+' + start, prev + int(start), int(start), num[i:]):
yield s, v
for s, v in self._helper(prefix + '-' + start, prev - int(start), -int(start), num[i:]):
yield s, v
mul_diff = diff * int(start)
for s, v in self._helper(prefix + '*' + start, (prev - diff) + mul_diff, mul_diff, num[i:]):
yield s, v
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
for s, v in self._helper('', 0, 0, num):
if v == target:
ans.append(s)
return ans
def main():
cases = [
# ("123456789", 45),
("105", 5),
("000", 0)
]
for case in cases:
print(case, Solution().addOperators(*case))
if __name__ == '__main__':
main()