palindrome-partitioning.go

// https://leetcode.com/problems/palindrome-partitioning

type pair struct {
    left, right int
}

func partition(s string) [][]string {
    chars := []rune(s)
    ch := make(chan pair)
    transitionTable := make([][]int, len(chars))
    
    go func() {
        for i, _ := range chars {
            expandCenter(chars, i, i, ch)
            expandCenter(chars, i, i + 1, ch)
        }
        
        close(ch)
    }()
    
    for x := range ch {
        transitionTable[x.left] = append(transitionTable[x.left], x.right)
    }
    
    result := [][]string{}
    generateCombinations(transitionTable, chars, 0, []string{}, &result)
    
    return result
}

func expandCenter(chars []rune, left, right int, ch chan<- pair) {
    for left >= 0 && right < len(chars) && chars[left] == chars[right] {
        ch <- pair{left, right}
        left--
        right++
    }
}

func generateCombinations(transitionTable [][]int, chars []rune, start int, seq []string, result *[][]string) {
    if start >= len(chars) {
        dst := make([]string, len(seq))
        copy(dst, seq)
        *result = append(*result, dst)
        
        return
    }
    
    for _, end := range transitionTable[start] {
        str := string(chars[start: end + 1])
        generateCombinations(transitionTable, chars, end + 1, append(seq, str), result)
    }
}