Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
The solution for this problem can be done with the help of DFS.
The logic is to loop through the string one by one. Once we find a palindromic string for the string str(0, i) we store the current string in “sub_result”. Then we recursively call “dfs” function to find palindrome string for rest of the sub string: subStr(i+1, length).
When we reach end of the string, copy the value in “sub_str” into “result” string.
Solution in C++
#include<iostream> #include<vector> #include<string> using namespace std; // function to check if a string is a palindrome or not bool isPalindrome(const string& s, int start, int end) { while(start <= end) { if(s[start++] != s[end--]) return false; } return true; } // function to perfor DFS // index = Start index of the string // given_string = Original string from input // sub_result = To store intermediate result // result = To return the final result void dfs(int index, string& given_string, vector<string>& sub_result, vector<vector<string> >& result) { if(index == given_string.size()) { result.push_back(sub_result); return; } for(int i = index; i < given_string.size(); ++i) { if(isPalindrome(given_string, index, i)) { sub_result.push_back(given_string.substr(index, i - index + 1)); dfs(i+1, given_string, sub_result, result); sub_result.pop_back(); } } } vector<vector<string>> get_partition(string given_string) { vector<vector<string> > result; if(given_string.empty()) return result; vector<string> sub_result; dfs(0, given_string, sub_result, result); return result; } int main() { string given_string = "aab"; vector< vector<string>> result = get_partition(given_string); cout<<"The result is = "<<endl; for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[0].size(); j++) { cout<< result[i][j]<<" "; } cout<<endl; } }
Output:
The result is = a a b aa b