forked from soapyigu/LeetCode-Swift
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ExpressionAddOperators.swift
50 lines (44 loc) · 1.72 KB
/
ExpressionAddOperators.swift
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
/**
* Question Link: https://leetcode.com/problems/expression-add-operators/
* Primary idea: Classic Depth-first Search, terminates at when position encounters the
* length of the string num, add to result when eval is equal to target
*
* Note:
* 1. String cast to Integer will make character loss, e.g. "05" -> 5
* 2. Multiplication's priority is higher than addiction
*
* Time Complexity: O(n!), Space Complexity: O(n)
*
*/
class ExpressionAddOperators {
func addOperators(_ num: String, _ target: Int) -> [String] {
var res = [String]()
let numChars = Array(num.characters)
guard numChars.count > 0 else {
return res
}
dfs(&res, "", numChars, target, 0, 0, 0)
return res
}
private func dfs(_ res: inout [String], _ temp: String, _ numChars: [Character], _ target: Int, _ pos: Int, _ eval: Int, _ mul: Int) {
if pos == numChars.count {
if eval == target {
res.append(temp)
}
return
}
for i in pos ..< numChars.count {
if i != pos && numChars[pos] == "0" {
break
}
let curt = Int(String(numChars[pos ..< i + 1]))!
if pos == 0 {
dfs(&res, temp + String(curt), numChars, target, i + 1, curt, curt)
} else {
dfs(&res, temp + "+" + String(curt), numChars, target, i + 1, eval + curt, curt)
dfs(&res, temp + "-" + String(curt), numChars, target, i + 1, eval - curt, -curt)
dfs(&res, temp + "*" + String(curt), numChars, target, i + 1, eval - mul + mul * curt, mul * curt)
}
}
}
}