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
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode131 分割回文串 golang

相关阅读 >>

jenkins构建Go及java项目

Go timer 是如何被调度的？

研究数组

锁的使用场景主要涉及到哪些？读写锁为什么会比普通锁快【Golang 入门系列十六】

Golang组件化网络服务器框架halia指南

Go 语言数据类型

【raspberry pi】编译安装etcd集群

2021-03-12：Go中，如何确定有没有内存泄露，系统里怎么去监控整体的运行情况，日志是怎么处理