# Practice Algorithm Using Golang W/ String-Slicing Problem

Thanks for looking at my problem I try to code this problem in golang:

Here is Code:

``````func partition(s string) [][]string {
return helper(0, s, nil, nil)
}

func helper(level int, s string, temp []string, res [][]string ) [][]string {
if level == len(s) {
el := make([]string, len(temp))
copy(el,  temp)
res = append(res, temp)
return res
}
for i:= level+1; i<= len(s); i++ {
if valid(s[level:i]) {
fmt.Println(level)
fmt.Println(s[level: i])
temp = append(temp, s[level:i])
res = helper(i, s, temp, res)
fmt.Println("res ",res)
temp = temp[:len(temp)-1]
}
}
return res
}

func valid(s string) bool {
if len(s) == 1 {
return true
}
for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
``````

Here is some console log debugging trace

``````0
c
1
b
2
c
3
c
res  [[c b c c]]
res  [[c b c c]]
2
cc
res  [[c b cc c] [c b cc]]
res  [[c b cc c] [c b cc]]
res  [[c b cc c] [c b cc]]
0
cbc
3
c
res  [[c b cc c] [c b cc] [cbc c]]
res  [[c b cc c] [c b cc] [cbc c]]
``````

Algorithm is basic DFS which temp as intermediate holder to contribute one piece result to final output.

if you try to use test case like “cbcc”, the output is [[“c”,“b”,“cc”,“c”],[“c”,“b”,“cc”],[“cbc”,“c”]], but expect answer is [[“c”,“b”,“c”,“c”],[“c”,“b”,“cc”],[“cbc”,“c”]], you can see that only first slice in slices have different output which “cc” should be “c”, I think the second one [“c”,“b”,“cc”] somehow override the previous existing one. I am not sure about string slice internally, but I believe since string in golang is immutable which is safe-slicing.
Which part is I am missing? Or any better way to handle string slicing in this case.

Strings are indeed immutable, but slices are not. Slices are views into underlying arrays. Two slices can thus share data - changing one changes the other. Each element in a `[]string` can change to contain another string. Please see:

https://blog.golang.org/go-slices-usage-and-internals

1 Like

Thanks for replying. If I am understanding right. For each recursive loop, I create new temp slice, which make sure each round slice won’t share reference, but which still give me same result. This failing test case is “ababbbabbaba”

``````func partition(s string) [][]string {
return helper(0, s, nil, nil)
}

func helper(level int, s string, temp []string, res [][]string ) [][]string {
if level == len(s) {
el := make([]string, len(temp))
copy(el,  temp)
res = append(res, temp)
return res
}
for i:= level+1; i<= len(s); i++ {
if valid(s[level:i]) {
//fmt.Println(level)
//fmt.Println(s[level: i])
temp := append(temp, s[level:i]) <- create copy of temp slice
res = helper(i, s, temp, res)
fmt.Println("res ",res)
temp = temp[:len(temp)-1]
}
}
return res
}

func valid(s string) bool {
if len(s) == 1 {
return true
}
for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
``````

debugging trace:

``````res  [[a b a b b b a b b a b a]]
res  [[a b a b b b a b b a b a]]
res  [[a b a b b b a b b a b a]]
res  [[a b a b b b a b b aba b a] [a b a b b b a b b aba]]
res  [[a b a b b b a b b aba b a] [a b a b b b a b b aba]]
``````

Any idea? Do you think it is good practice to create new copy of variable in recursive function?

No. `append` may return a slice referencing the same backing array as the first parameter. The slices are different, but `temp` can refer to the same element both before and after the `append`.

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.