Algorithm
Problem Name: 131. Palindrome Partitioning
Given a string s, partition s such that every substringof the partition is a palindrome Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
Constraints:
1 <= s.length <= 16scontains only lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int start;
int len;
} buff_t;
typedef struct {
char ***p;
int *csz;
int psz;
int pn;
} res_t;
void add2res(res_t *res, const char *s, buff_t *buff, int d) {
int i;
char *str, **pp;
if (res->psz == res->pn) {
res->psz = (res->psz == 0) ? 10 : res->psz * 2;
res->p = realloc(res->p, res->psz * sizeof(char **));
res->csz = realloc(res->csz, res->psz * sizeof(int));
//assert(res->p && res->psz);
}
pp = malloc(d * sizeof(char *));
//assert(pp);
for (i = 0; i < d; i ++) {
str = strndup(&s[buff[i].start], buff[i].len);
pp[i] = str;
}
res->p[res->pn] = pp;
res->csz[res->pn ++] = d;
}
int is_palindrome(const char *s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return 0;
start ++;
end --;
}
return 1;
}
void bt(const char *s, int start, int sz, buff_t *buff, int d, res_t *res) {
int i;
if (start == sz) {
// done, save result
add2res(res, s, buff, d);
return;
}
for (i = start; i < sz; i ++) {
if (is_palindrome(s, start, i)) {
buff[d].start = start;
buff[d].len = i - start + 1;
bt(s, i + 1, sz, buff, d + 1, res);
}
}
}
char*** partition(char* s, int** columnSizes, int* returnSize) {
res_t res = { 0 };
buff_t *buff;
int sz;
sz = strlen(s);
buff = malloc(sz * sizeof(buff_t));
//assert(buff);
bt(s, 0, sz, buff, 0, &res);
//free(buff);
*columnSizes = res.csz;
*returnSize = res.pn;
return res.p;
}
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<string>> partition(string s) {
vector < vector<string>>res;
vector < string>v;
dfs(s, 0, v, res);
return res;
}
void dfs(string s, int pos, vector < string>& v, vector<vector<string>>& res){
if(pos >= s.size()){
res.push_back(v);
return;
}
for(int i = pos; i < s.size(); i++){
int l = pos, r = i;
bool b = true;
while(l < r && b) if(s[l++] != s[r--]) b = false;
if(b){
v.push_back(s.substr(pos, i - pos + 1));
dfs(s, i + 1, v, res);
v.pop_back(>;
}
}
}
};
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
#3 Code Example with Java Programming
Code -
Java Programming
start coding...
class Solution {
public List();
helper(ans, new ArrayList(), a, 0);
return ans;
}
private void helper(List < List temp, String a, int idx) {
if (idx == a.length()) {
ans.add(new ArrayList<>(temp));
return;
}
for (int i=idx; i < a.length(); i++) {
String sb = a.substring(idx, i+1);
if (isPalindrome(sb)) {
temp.add(sb);
helper(ans, temp, a, i+1);
temp.remove(temp.size()-1);
}
}
}
private boolean isPalindrome(String s) {
return new StringBuilder(s).reverse().toString().equals(s);
}
}
Input
s = "a"
Output
[["a"]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const partition = function(s) {
let res = []
backtrack(res, [], 0, s)
return res
}
function backtrack(res, cur, start, s) {
if (start === s.length) res.push([...cur])
else {
for (let i = start; i < s.length; i++) {
if (isPalindrome(s, start, i)) {
cur.push(s.substring(start, i + 1))
backtrack(res, cur, i + 1, s)
cur.pop()
}
}
}
}
function isPalindrome(str, start, i) {
let l = start,
r = i
while (l < r) {
if (str[l] !== str[r]) return false
l++
r--
}
return true
}
Input
s = "a"
Output
[["a"]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def partition(self, s):
q, n = [[s[0]]], len(s)
for i in range(1, n):
new = []
for arr in q:
cur = arr[-1] + s[i]
if i < n - 1 or cur == cur[::-1]:
new.append(arr[:-1] + [cur])
if arr[-1] == arr[-1][::-1]:
new.append(arr + [s[i]])
q = new
return q
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0131_PalindromePartitioning
{
public IList < IList(), results, dp, 0, s);
return results;
}
private void GenerateResult(List < string> current_result, List(current_result));
return;
}
for (int i = position; i < s.Length; i++)
{
if (dp[position, i])
{
current_result.Add(s.Substring(position, i - position + 1));
GenerateResult(current_result, results, dp, i + 1, s);
current_result.RemoveAt(current_result.Count - 1);
}
}
}
}
}
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]