forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathadd_operators.py
More file actions
86 lines (75 loc) · 2.19 KB
/
add_operators.py
File metadata and controls
86 lines (75 loc) · 2.19 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""
Expression Add Operators
Given a string of digits and a target value, return all possibilities to
insert binary operators (+, -, *) between the digits so they evaluate to
the target value.
Reference: https://leetcode.com/problems/expression-add-operators/
Complexity:
Time: O(4^n) worst
Space: O(n) recursion depth
"""
from __future__ import annotations
def add_operators(digits: str, target: int) -> list[str]:
"""Return all expressions formed by inserting +, -, * that equal target.
Args:
digits: A string containing only digits 0-9.
target: The target integer value.
Returns:
A list of valid expression strings.
Examples:
>>> add_operators("123", 6)
['1+2+3', '1*2*3']
"""
result: list[str] = []
if not digits:
return result
_dfs(result, "", digits, target, 0, 0, 0)
return result
def _dfs(
result: list[str],
path: str,
digits: str,
target: int,
position: int,
evaluated: int,
multed: int,
) -> None:
"""Depth-first search helper that builds expressions recursively."""
if position == len(digits):
if target == evaluated:
result.append(path)
return
for i in range(position, len(digits)):
if i != position and digits[position] == "0":
break
current = int(digits[position : i + 1])
if position == 0:
_dfs(result, path + str(current), digits, target, i + 1, current, current)
else:
_dfs(
result,
path + "+" + str(current),
digits,
target,
i + 1,
evaluated + current,
current,
)
_dfs(
result,
path + "-" + str(current),
digits,
target,
i + 1,
evaluated - current,
-current,
)
_dfs(
result,
path + "*" + str(current),
digits,
target,
i + 1,
evaluated - multed + multed * current,
multed * current,
)