131. 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
.
A palindrome string is a string that reads the same backward as forward.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
Constraints:
1 <= s.length <= 16
s
contains only lowercase English letters.
The solution to the above problem is
class Solution {
public:
vector<vector<string>>ans;
bool checkPalindrome(string s,int start,int end){
while(start<=end){
if(s[start]!=s[end]){
return false;
}
start++;
end--;
}
return true;
}
void helper(string s,int t,vector<string>&temp){
if(t==s.size()){
ans.push_back(temp);
return;
}
for(int i=t; i<s.length(); i++){
if(checkPalindrome(s,t,i)){
temp.push_back(s.substr(t,i-t+1));
helper(s,i+1,temp);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<string>v;
helper(s,0,v);
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.