需求

要求输入一个字符串，将此字符串分割成一些子串，使每个子串都是回文串(单字符的字符串也属于回文串)。

例如输入字符串"abb"，则返回：

["a", "b", "b"],
["a", "bb"]，

思路

本题的核心是将字符串分割出多个回文的子字符串。判断某个字符串是不是回文字符串非常简单，我们直接将字符串进行逆序，然后判断与原字符串是否相同即可。 对字符串进行分割的过程实际上是一个递归的过程，解决本题使用递归函数将非常容易。

实现

package chapter07

// 判断是否回文
func isPal(s string) bool {
    return s == reverse(s)
}

// 字符串倒序
func reverse(s string) string {
    r := []rune(s)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}

// 递归进行分割
func clipStr(start int, s []rune, l [][]rune, res [][][]rune) [][][]rune {
    // 如果已经到达字符串的末尾，则将结果添加到结果集中
    if start > len(string(s))-1 {
        res = append(res, l)
        return res
    }

    for i := start + 1; i < len(s)+1; i++ {
        // 如果是回文，递归继续分割
        if isPal(string(s[start:i])) {
            res = clipStr(i, s, append(l, s[start:i]), res)
        }
    }
    return res
}

func partition(str string) [][]string {
    var res [][][]rune
    res = clipStr(0, []rune(str), [][]rune{}, [][][]rune{})
    var ret [][]string
    for _, v := range res {
        var s []string
        for _, vv := range v {
            s = append(s, string(vv))
        }
        ret = append(ret, s)
    }
    return ret
}