首页 > 代码库 > 【Lintcode】136.Palindrome Partitioning
【Lintcode】136.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.
Example
Given s = "aab"
, return:
[
["aa","b"],
["a","a","b"]
]
题解:
Solution 1 ()
class Solution { public: vector<vector<string>> partition(string s) { if (s.empty()) { return {{}}; } vector<vector<string> > res; vector<string> v; dfs(res, v, s, 0); return res; } void dfs(vector<vector<string> > &res, vector<string> &v, string s, int pos) { if (pos >= s.size()) { res.push_back(v); return; } string str; for (int i = pos; i < s.size(); ++i) { str += s[i]; if (isValid(str)) { v.push_back(str); dfs(res, v, s, i + 1); v.pop_back(); } } } bool isValid(string str) { if (str.empty()) { return true; } int begin = 0; int end = str.size() - 1; for (; begin <= end; ++begin, --end) { if (str[begin] != str[end]) { return false; } } return true; } };
Solution 1.2 ()
class Solution { public: bool isPalindrome(string &s, int i, int j){ while(i < j && s[i] == s[j]){ i++; j--; } if(i >= j) { return true; } else { return false; } } void helper(vector<vector<string>> & res, vector<string> &cur, string &s, int pos){ if(pos == s.size()){ res.push_back(cur); return; } for(int i = pos; i <= s.size() - 1; i++){ if(isPalindrome(s, pos, i)){ cur.push_back(s.substr(pos, i - pos + 1)); helper(res, cur, s, i+1); cur.pop_back(); } } } vector<vector<string>> partition(string s) { vector<vector<string>> res; vector<string> cur; helper(res, cur, s, 0); return res; } };
【Lintcode】136.Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。