【算法】分割出回文字符串

需求

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

例如输入字符串"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
}