首页 > 代码库 > leetcode Palindrome Partitioning
leetcode Palindrome Partitioning
把一个字符串划分成几个回文子串，枚举所有可能的划分
例如
For example, given s = "aab",
Return
[ ["aa","b"], ["a","a","b"] ]
写一个子函数判断是否为回文。
然后dfs，这个dfs比之前的稍微难理解一些。dfs函数每次输入的起点代表之前已经处理好了，从这个起点开始到结尾len的有几种长度可能组成，回文的都要dfs遍历一次，如果没有就++。例如输入为abcc，假设此时start指向b了，那么b是回文，要dfs从start+1开始，因为b的长度为1，一直继续。。。之后还要回到b开始长度为2的串也就是bc然后不是回文，再判断bcc不是回文。这里嵌套着的还是要好好理解。
class Solution {public: //131 bool isPalindrome131(string str) { int len = str.size(); if (len <= 1) return true; int i = 0; while (i <= len / 2) { if (str[i] != str[len - i - 1]) return false; i++; } return true; } void dfs131(vector<vector<string> > &ans, vector<string> &tmp, string &s, int start) { int len = s.size(); if (start >= len) {ans.push_back(tmp); return;} for (int i = 1; i <= len - start; i++) if (isPalindrome131(s.substr(start, i))) { tmp.push_back(s.substr(start, i)); dfs131(ans, tmp, s, start + i); tmp.pop_back(); } } vector<vector<string> > partition(string s) { int len = s.size(); vector<vector<string> > ans; if (len == 0) return ans; vector<string> tmp; dfs131(ans, tmp, s, 0); return ans; }};
leetcode Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。