首页 > 代码库 > [Leetcode]Palindrome Partitioning
[Leetcode]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"] ]
[解题思路]
由于要求列出所有的可能,直接上dfs
[代码]
class Solution { public: vector<vector<string> > res; vector<vector<string>> partition(string s) { vector<string> partitions; dfs(partitions, s, 0); return res; } void dfs(vector<string> partitions, string &s, int idx) { if (idx >= s.size()) { if (partitions.size() > 0) { res.push_back(partitions); } return; } for (int i = idx; i < s.size(); ++i) { string cur = s.substr(idx, i - idx + 1); if (isPalindrome(cur)) { partitions.push_back(cur); dfs(partitions, s, i + 1); partitions.pop_back(); } } return; } bool isPalindrome(string s) { int len = s.size(); if (len <= 1) return true; int left = 0; int right = len - 1; while (left < right) { if (s[left] != s[right]) return false; ++left; --right; } return true; } };
[Leetcode]Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。