Practice Algorithm Using Golang W/ String-Slicing Problem

[Peng_Yan]

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

Palindrome Partitioning

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.

[calmh (Jakob Borg)]

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

[Peng_Yan]

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?

[calmh (Jakob Borg)]

@Peng_Yan

temp := append(temp, s[level:i]) <- create copy of temp slice

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