找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1542|回复: 0
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Palindrome Partitioning II】-【刷题第一弹】

[复制链接]

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 10-22-2014 05:53 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-22-2014 12:19 AM 编辑

快速通道:
https://oj.leetcode.com/problems/palindrome-partitioning-ii/

题目:

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

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

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

思路:

典型DP题。此题在保证O(n^2)时间复杂度的前提下至少有两种方法可解。 设d[i ][j]为S[i..j]最小分割数,则d[i ][j] = min(d[i ][t-1] | S[t..j]为回文), (i <= t <= j), 用滚动数组可将d由二维化为一维,但判断S[t..j]是否为回文的方法决定了最终空间复杂度。我用的是从中间向两边边展开边判断是否字母对称的方法来判断回文,此法在判断的同时更新d数组,无需存储回文判断的结果,故可保证最终算法空间复杂度为O(n).

代码:

  1. int minCut(string s) {
  2.     int len = s.size();
  3.     if (len == 0)
  4.         return 0;
  5.    
  6.     vector<int> subMins(len+1);
  7.     for (int i = 0; i <= len; ++i)
  8.         subMins【i】 = i - 1;
  9.    
  10.     for (int i = 0; i < len; ++i)
  11.     {
  12.         //Check possible palindromes of odd length
  13.         for (int j = 0; (i - j >= 0) && (i + j < len) && (s[i-j] == s[i+j]); ++j)
  14.             subMins[i+j+1] = min(subMins[i+j+1], subMins[i-j] + 1);

  15.         //Check possible palindromes of even length
  16.         for (int j = 0; (i - j >= 0) && (i + 1 + j < len) && (s[i-j] == s[i+j+1]); ++j)
  17.             subMins[i+j+2] = min(subMins[i+j+2], subMins[i-j] + 1);
  18.     }
  19.     return subMins[len];
  20. }
复制代码

注意代码中的subMins便是上边提到的d数组。
时间复杂度:O(n^2)
空间复杂度:O(n)

本帖被以下淘专辑推荐:

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表