Chinaunix首页 | 论坛 | 博客
  • 博客访问: 121156
  • 博文数量: 53
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 620
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-24 16:22
文章存档

2014年(53)

我的朋友

分类: C/C++

2014-09-18 15:36:24

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"]
  ]



Have you been asked this question in an interview? 
这道题很值得推敲。首先给出先dp再dfs的方法,直接tls了,这里的dp比较粗暴,是计算字符串中所有字符是不是回文。估计这个地方消耗了很多时间,然后是dfs,dfs利用之前找到的dp数组,判断某段字符串是不是回文,然后形成了一颗dfs的树,在这些树里找问题的解。
这里总结下dfs:dfs其实是一种特殊的递归,只不过通常的递归是这样的:
fun(){
...
     fun();
...
}
而dfs是这样的:
fun(){
...
     for(int i=0;i
          fun();
     }
...
}
dfs每次运行到for的时候,它的解空间都分叉成n支,然后每一支又分叉成n支,这就形成了解空间的树。而dfs是深度优先访问这棵树的,这也是它的名字的由来。
通过dfs,我们考察了解的所有可能性,下面是code:

  1. void dfs(string s, vector<string> &path, vector<vector<string>> &res)
  2.     {
  3.         if(s.size() < 1)
  4.         {
  5.             res.push_back(path);
  6.             return;
  7.         }
  8.         for(int i = 0; i < s.size(); i++)
  9.         {
  10.             int begin = 0;
  11.             int end = i;
  12.             while(begin < end)
  13.             {
  14.                 if(s[begin] == s[end])
  15.                 {
  16.                     begin++;
  17.                     end--;
  18.                 }
  19.                 else
  20.                     break;
  21.             }
  22.             if(begin >= end)//bool isPalindrome = true;
  23.             {
  24.                 path.push_back(s.substr(0,i+1));
  25.                 dfs(s.substr(i+1),path,res);
  26.                 path.pop_back();
  27.             }
  28.         }
  29.     }
  30.     vector<vector<string>> partition(string s) {
  31.         vector<vector<string>> res;
  32.         vector<string> path;
  33.         dfs(s,path,res);
  34.         return res;
  35.     }


阅读(783) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~