131分隔回文串.md

func partition(s string) [][]string {
    var res [][]string
    var path []string
    var backtrack func(start int)
    backtrack = func(start int) {
        // 终止条件 当分隔点start已经到达尾部时
        if start == len(s) {
            tmp := make([]string, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i := start; i < len(s); i++ {
            // 当是回文时存入path，否则继续往前走
            if isPalindrome(s, start, i) {
                path = append(path, s[start : i+1])
            } else {
                continue
            }
            // 回溯
            backtrack(i+1)
            path = path[:len(path)-1]
        }
    }
    backtrack(0)
    return res
}

// 判断是否为回文
func isPalindrome(s string, start, end int) bool {
    for start <= end {
        if s[start] != s[end] {
            return false
        }
        start++
        end--
    }
    return true
}