dp、dfs：131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

动态规划找出所有回文子串

• 状态方程式

l:左索引 r:右索引
dp[l][r] = (s[l] == s[r] and (r-j<=2 or dp[l+1][r-1])

深度搜索

• 每次深度回归需注意remove结尾子回文串，防止影响下一组搜索

切片拷贝问题

• 使用append到结果二位数组时，如果切片没有引起内存重新分配，那么添加的数据可能会被改变

在slice中，当len小于cap 的值的时候， 进行append 操作是不会造成内存的重新分配。

type Solution struct {
    l int
    ret  [][]string
    dp  [][]bool
    str string
    p []string
}

func (s *Solution) Dfs (i int, tmp []string) {
    if i == s.l {
        s.p = make([]string, len(tmp))
        copy(s.p, tmp)
        s.ret = append(s.ret, s.p)
    }

    for j := i; j < s.l; j++ {
        if s.dp[i][j] {
            tmp = append(tmp, s.str[i:j+1])
            s.Dfs(j+1, tmp)
            tmp = tmp[:len(tmp)-1]
        }
    }
}


func (t *Solution)  Partition(s string) [][]string {
    t.l = len(s)
    t.str = s

    // 构建初始状态
    for i := 0; i < t.l; i++ {
        tmp := make([]bool, t.l)
        t.dp = append(t.dp, tmp)
    }

    // dp
    for i := 0 ; i < t.l; i++ {
        for j := 0; j <= i; j++ {
            if s[i] == s[j] && (i-j < 2 || t.dp[j+1][i-1]) {
                t.dp[j][i] = true
            }
        }
    }


    t.ret = [][]string{}
    fmt.Println(t.dp)
    t.Dfs(0, []string{})

    return t.ret
}

func partition(s string) [][]string {
    solution := Solution{}

    return solution.Partition(s)
}