找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1608|回复: 5
收起左侧

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

[复制链接]

3

主题

5

精华

272

积分

高级会员

Rank: 3Rank: 3

积分
272
发表于 10-7-2014 08:16 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 allenus 于 10-7-2014 10:55 AM 编辑

快速通道:
www.oj.leetcode.com/problems/palindrome-partitioning/
题目:

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [    ["aa","b"],    ["a","a","b"]  ]

Hint:


本题的Intuitive 解法是用recursion,即以某一个字符为起点,找到一个palindrome,再从palindrome的下一个字符开始继续找palindrome,直到字符串结尾。但是recursion 对于大数据测试显然太慢。于是我们寻求 dynamic programming 的解法。

一种解法是建立一个N*N的palindrome的表,第一行表示长度为一的palindrome,显然每个字符都符合。第二行记录长度为2的substring是否为palindrome。即检查char(i) == char(i + 1). 然后依次类推,填满表格,直到长度为N的substring,即原字符串。在检查长度为L的 substring 时,递归算法为 b[i + L - 1] = true if b[i + 1][ i + L - 2] = true && char(i) == char(i + L -1). 最终 1/2 N^2 次运算填满半个表格(上三角)。

然后以此表格为基础,用recursion 来trace back,恢复出palindrome组合。从 index = 0开始,每次check 从这个index 起始的所有 palindrome,最多check N次,然后从每一个palindrome 的下一个字符开始,再继续寻找palindrome,直到字符串末尾。每下一级recursion 向上一级返回所有合理的palindrome 数组,依次汇集。

  1. public List<List<String>> partition(String s) {
  2.         final int n = s.length();
  3.         if (n == 0)
  4.             return new ArrayList<List<String>>();

  5.         boolean[][] b = new boolean[n][n];
  6.         for (int i = 0; i < n - 1; i++) {
  7.             b[i][i] = true;
  8.             b[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
  9.         }
  10.         b[n - 1][n - 1] = true;

  11.         for (int i = 3; i <= n; i++) {
  12.             for (int x = 0; x < n + 1 - i; x++) {
  13.                 if (s.charAt(x) == s.charAt(x + i - 1))
  14.                     b[x][x + i - 1] = b[x + 1][x + i - 2];
  15.             }
  16.         }

  17.         return trace(b, s, 0);
  18.     }

  19.     List<List<String>> trace(boolean[][] b, String s, int l) {
  20.         int n = s.length();
  21.         List<List<String>> out = new ArrayList<List<String>>();

  22.         if (b[l][n - 1]) {
  23.             List<String> a = new ArrayList<String>();
  24.             a.add(s.substring(l));
  25.             out.add(a);
  26.         }

  27.         for (int i = l; i < n - 1; i++) {
  28.             if (b[l][i]) {
  29.                 List<List<String>> t = trace(b, s, i + 1);
  30.                 for (int j = 0; j < t.size(); j++)
  31.                     t.get(j).add(0, s.substring(l, i + 1));
  32.                 out.addAll(t);
  33.             }
  34.         }
  35.         return out;
  36.     }
复制代码

复杂度:建立表格 O(N^2)。

Recursion 恢复palindrome 数组,worst case O(N^N),例如“aaaaaaaaaaaaaaaaaaaaaaa”。不确定是否有误或者改进方法,但是实际情况是,平均时间远低于O(N^N),因为palindrome 一般比较少。



建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)

===============
点此查看汇总贴
===============




本帖被以下淘专辑推荐:

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 12-5-2014 03:57 AM | 显示全部楼层
我发个暴力法的,好理解一些
  1. class Solution {
  2. public:
  3.     vector<vector<string>> partition(string s) {
  4.         vector<vector<string> > paths;
  5.         vector<string> path;
  6.         partitionDfs(0, path, paths, s);
  7.         return paths;
  8.     }
  9.    
  10.     void partitionDfs(int start, vector<string> &path, vector<vector<string> > &paths, const string &s){
  11.         if(start == s.length()){
  12.             paths.push_back(path);
  13.             return;
  14.         }
  15.         
  16.         for(int i = start; i < s.length(); i++){
  17.             if(isPalindrome(s, start, i)){
  18.                 path.push_back(s.substr(start, i - start + 1));
  19.                 partitionDfs(i + 1, path, paths, s);
  20.                 path.pop_back();
  21.             }
  22.         }
  23.     }
  24.    
  25.     bool isPalindrome(const string &s, int start, int end){
  26.         for(; start < end; start++, end--){
  27.             if(s[start] != s[end]) return false;
  28.         }
  29.         return true;
  30.     }
  31. };
复制代码

补充内容 (12-5-2014 04:09 AM):
时间复杂度感觉是O(2^n),求大神来证明

补充内容 (12-5-2014 04:12 AM):
时间复杂度感觉应该是O(2^n),但不会证明,求大神
回复 支持 反对

使用道具 举报

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-8-2014 07:42 PM | 显示全部楼层
回复 支持 反对

使用道具 举报

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

本版积分规则

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