131.分割回文串

CharlseGo / 2024-09-26 / 原文

点击查看代码

func partition(s string) [][]string {
    // 1.判断0值输入
    if s == "" {
        return [][]string{}
    }
    res := [][]string{}
    path := []string{}

    // 调用回溯函数
    backtracking(s, 0, &res, path)

    return res
}

func backtracking(str string, startIndex int, res *[][]string, path []string) {
    // 到达叶子结点，说明成功找到了一个划分方案
    if startIndex >= len(str) {
        temp := make([]string, len(path))
        copy(temp, path)
        *res = append(*res, temp)
        return
    }

    // 正常递归回溯过程
    for i := startIndex; i < len(str); i++ {
        // 如果区间内是回文串.左闭右开
        if isPalindrom(str[startIndex : i+1]) {
            path = append(path, str[startIndex:i+1])
            // 递归调用，i+1是下一个起始位置
            backtracking(str, i+1, res, path)
            // 回溯，撤销选择。因为一次回溯之后，必须回到上一步的状态，进行其他可能性的寻找
            path = path[:len(path)-1]
        }
    }
}

func isPalindrom(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}