leetcode131 分割回文串 golang

131. 分割回文串

解题思路

利用动态规划，遍历所有可能的字符串，标记其是否是回文字符串。

然后利用回溯（dfs）进行，依次查找，并记录过程中所有可能的字符串。最红输出即可。

注意,这里的 dp[i][j]的定义是和字符串s[i:j] 保持一致的:前闭后开。

代码

var ans [][]string
func partition(s string) [][]string {
    dp := make([][]bool,len(s))
    for i:=range dp{
        dp[i]=make([]bool,len(s)+1)
        dp[i][i+1]=true
        dp[i][i]=true
    }
    for l := 2;l<=len(s);l++{
        for i:=0;i+l<=len(s);i++{
            j:=i+l
            dp[i][j]= (s[i]==s[j-1])&&dp[i+1][j-1]
        }
    }


    ans = make([][]string,0,16)
    
    dfs(s,0,nil,dp)
    return ans
    
}

func dfs(s string,i int,list []string,dp [][]bool){
    if i == len(s){
        ans = append(ans, append([]string{}, list...))
        return
    }
    for j:=i+1;j<=len(s);j++{
        if dp[i][j]{
            dfs(s,j,append(list,s[i:j]),dp)
        }
    }
    return
}