Leetcode--Palindrome Partitioning II

Problem Description:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

分析:设cut[i] = 区间[0,i]之间最小的cut数,n为字符串长度, 则,
cut[i] = min(cut[i],1+cut[j] ) 0 有个转移函数之后,一个问题出现了,就是如何判断[j,i]是否是回文?每次都从i到j比较一遍?太浪费了,这里也是一个DP问题。
定义函数
flag[i][j] = true if [i,j]为回文
那么
flag[i][j] = str[i] == str[j] && P[i+1][j-1];

class Solution { public: int minCut(string s) { //if(s.size()==0) // return 0; int n=s.size(); vector > flag(n,vector(n,0)); vector cut(n+1); for(int i=0;i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:uva 10870 Recurrences
下一篇:BZOJ 2662 BeiJing wc2012 冻结
相关文章

LeetCode——Palindrome Partitioning

[LeetCode] Palindrome Partitionin

Palindrome Partitioning

[LeetCode]Palindrome Partitioning II

[LeetCode]Palindrome Partitioning

C++程序的设计机制3: RAII机制

ASCII码排序 STL练手题

由UIImageView中的UIButton不响应事件

UIImage 压缩

hdu_2000_ASCII码排序_解题报告

图文推荐

Leetcode--Palindrome Partitioning II
ZOJ 3640 Help Me
Leetcode--Palindrome Partitioning II
CF 518C(Anya and
Leetcode--Palindrome Partitioning II
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-02 人气:4
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.077 (s). 10 q(s)