131. Palindrome Partitioning
Palindrome Partitioning 131
2023-09-11 14:22:45 时间
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
Approach #1: backtracking. [C++]
class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> ans; if (s.length() == 0) return ans; vector<string> path; dfs(s, 0, ans, path); return ans; } private: void dfs(const string s, int idx, vector<vector<string>>& ans, vector<string>& path) { if (s.length() == idx) { ans.push_back(path); return; } for (int i = idx; i < s.length(); ++i) { if (isPalindrome(s, idx, i)) { path.push_back(s.substr(idx, i-idx+1)); // this is the point code in this problem. dfs(s, i+1, ans, path); path.pop_back(); } } } bool isPalindrome(const string s, int start, int end) { while (start <= end) { if (s[start++] != s[end--]) return false; } return true; } };
相关文章
- Palindrome Number
- Codeforces Round #277(Div. 2) (A Calculating Function, B OR in Matrix, C Palindrome Transformation)
- POJ 3280 Cheapest Palindrome(DP 回文变形)
- 【LeetCode算法-9】Palindrome Number
- 【LeetCode】9. Palindrome Number
- 【Codeforces Global Round 7 D1】Prefix-Suffix Palindrome (Easy version)
- 【Codeforces 600C】Make Palindrome
- 【codeforces 752D】Santa Claus and a Palindrome
- LeetCode 125 Valid Palindrome(有效回文)(*)
- 【LeetCode】Palindrome Partitioning 解题报告
- Codeforces Round #311 (Div. 2) E - Ann and Half-Palindrome(字典树+dp)
- Codeforces Round #410 (Div. 2) A. Mike and palindrome
- Mutual Training for Wannafly Union #8 D - Mr.BG Hates Palindrome 取余
- leetcode 9. Palindrome Number