没有合适的资源?快使用搜索试试~ 我知道了~
132. 分割回文串 II
0 下载量 190 浏览量
2021-01-07
22:31:35
上传
评论
收藏 30KB PDF 举报
温馨提示
试读
2页
链接 题目. 难度: high 解答: dp用来表示前n个字符串最小需要多少次cut。另外先计算好各个子字符串是否是回文.之前想到过一个dp[i][j]表示是s[i:j+1]最少需要多少次切割。这个思路是对的,但是复杂度变为n**3了,没有利用到最后一次右边的字符串一定是回文的特性。 package main import fmt func minCut(s string) int { if len(s) <= 1 { return 0 } palis := make([][]bool, len(s)) for i := 0; i < len(s); i++ { palis
资源详情
资源评论
资源推荐
132. 分割回文串分割回文串 II
链接链接
题目.
难度难度:
high
解答:解答:
dp用来表示前n个字符串最小需要多少次cut。另外先计算好各个子字符串是否是回文.之前想到过一个dp[i][j]表示是s[i:j+1]最少
需要多少次切割。这个思路是对的,但是复杂度变为n**3了,没有利用到最后一次右边的字符串一定是回文的特性。
package main
import "fmt"
func minCut(s string) int {
if len(s) <= 1 {
return 0
}
palis := make([][]bool, len(s))
for i := 0; i < len(s); i++ {
palis[i] = make([]bool, len(s))
}
for j := 0; j = 0; i-- {
if s[i] == s[j] && (j-i < 3 || palis[i+1][j-1]) {
palis[i][j] = true
}
}
}
if palis[0][len(s)-1] {
return 0
}
dp := make([]int, len(s))
dp[0] = 0
for j := 1; j 0; i-- {
if palis[i][j] && (dp[i-1]+1) < dp[j] {
dp[j] = dp[i-1] + 1
}
}
}
return dp[len(s)-1] }
func main() {
fmt.Println(minCut("cdd"))
}
复杂度分析复杂度分析
time
O(n*n)
space
O(n*n)
执行结果执行结果
执行用时 :
8 ms
, 在所有 Go 提交中击败了
60.87%
的用户
weixin_38632825
- 粉丝: 3
- 资源: 948
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0