Partitioning is another classical problem which can be solved with backtracking algorithm.
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
| func partition(s string) [][]string {
result := [][]string{}
path := []string{}
length := len(s)
isParlindrom := func(s string) bool {
for i, j := 0, len(s) - 1; i < j; i, j := i + 1, j - 1 {
if s[i] != s[j] {
return false
}
}
return true
}
var backtracking func(int)
backtracking = func(index int) {
if index == length {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
for i := index; i < length; i++ {
if isParlindrom(s[index:i + 1]) {
path = append(path, s[index: i + 1])
backtracking(i + 1)
path = path[:len(path) - 1]
}
}
}
backtracking(0)
return result
}
|
We need to consider the edge case that some numbers start with 0 since golang’s strconv.Atoi will convert those string to integer successfully.
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
| import (
"strings"
"strconv"
)
func restoreIpAddresses(s string) []string {
result := []string{}
path := []string{}
length := len(s)
var backtracking func(int)
backtracking = func(index int) {
if index > length {
return
} else if len(path) == 4 {
if index == length {
result = append(result, strings.Join(path, "."))
}
return
}
for i := index; i < length; i++ {
if i - index <= 2 {
num, _ := strconv.Atoi(s[index:i + 1])
if (i - index == 2 && num < 100) || (i - index == 1 && num < 10) {
continue
}
if num < 256 {
path = append(path, s[index:i + 1])
backtracking(i + 1)
path = path[:len(path) - 1]
}
}
}
}
backtracking(0)
return result
}
|