#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char ***rows;
int *colSizes;
int size;
int cap;
} Result;
static bool isPalindrome(const char *s, int l, int r) {
while (l < r)
if (s[l++] != s[r--])
return false;
return true;
}
static void save(Result *res, char **path, int pathSize) {
if (res->size == res->cap) {
res->cap = res->cap ? 2 * res->cap : 16;
res->rows = realloc(res->rows, res->cap * sizeof(char **));
res->colSizes = realloc(res->colSizes, res->cap * sizeof(int));
}
char **row = malloc(pathSize * sizeof(char *));
for (int i = 0; i < pathSize; i++)
row[i] = strdup(path[i]);
res->rows[res->size] = row;
res->colSizes[res->size++] = pathSize;
}
static void backtrack(const char *s, int n, int start, char **path,
int pathSize, Result *res) {
if (start == n) {
save(res, path, pathSize);
return;
}
for (int i = start; i < n; i++) {
if (!isPalindrome(s, start, i))
continue;
path[pathSize] = strndup(s + start, i - start + 1);
backtrack(s, n, i + 1, path, pathSize + 1, res);
free(path[pathSize]);
}
}
char ***partition(char *s, int *returnSize, int **returnColumnSizes) {
Result res = {0};
int n = strlen(s);
char **path = malloc((n ? n : 1) * sizeof(char *)); // at most n pieces
backtrack(s, n, 0, path, 0, &res);
free(path);
*returnSize = res.size;
*returnColumnSizes = res.colSizes;
return res.rows;
}
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtrack(s, 0, path, result);
return result;
}
private:
void backtrack(const string &s, int start, vector<string> &path,
vector<vector<string>> &result) {
if (start == (int)s.size()) {
result.push_back(path);
return;
}
for (int i = start; i < (int)s.size(); i++) {
if (!isPalindrome(s, start, i))
continue;
path.push_back(s.substr(start, i - start + 1));
backtrack(s, i + 1, path, result);
path.pop_back();
}
}
bool isPalindrome(const string &s, int l, int r) {
while (l < r)
if (s[l++] != s[r--])
return false;
return true;
}
};
package backtracking
func partition(s string) [][]string {
var result [][]string
var path []string
var backtrack func(start int)
backtrack = func(start int) {
if start == len(s) {
result = append(result, append([]string(nil), path...))
return
}
for i := start; i < len(s); i++ {
if !isPalindrome(s, start, i) {
continue
}
path = append(path, s[start:i+1])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}
func isPalindrome(s string, l, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l, r = l+1, r-1
}
return true
}
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (!isPalindrome(s, start, i)) {
continue;
}
path.add(s.substring(start, i + 1));
backtrack(s, i + 1, path, result);
path.remove(path.size() - 1);
}
}
private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r--)) {
return false;
}
}
return true;
}
}
const isPalindrome = (s, l, r) => {
while (l < r) if (s[l++] !== s[r--]) return false;
return true;
};
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function (s) {
const result = [];
const path = [];
const backtrack = (start) => {
if (start === s.length) {
result.push([...path]);
return;
}
for (let i = start; i < s.length; i++) {
if (!isPalindrome(s, start, i)) continue;
path.push(s.slice(start, i + 1));
backtrack(i + 1);
path.pop();
}
};
backtrack(0);
return result;
};
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
result: List[List[str]] = []
path: List[str] = []
def backtrack(start: int) -> None:
if start == len(s):
result.append(path[:])
return
for i in range(start, len(s)):
if not self.isPalindrome(s, start, i):
continue
path.append(s[start : i + 1])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
def isPalindrome(self, s: str, l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
impl Solution {
pub fn partition(s: String) -> Vec<Vec<String>> {
let mut result = Vec::new();
let mut path = Vec::new();
Self::backtrack(s.as_bytes(), 0, &mut path, &mut result);
result
}
fn backtrack(s: &[u8], start: usize, path: &mut Vec<String>, result: &mut Vec<Vec<String>>) {
if start == s.len() {
result.push(path.clone());
return;
}
for i in start..s.len() {
if !Self::is_palindrome(s, start, i) {
continue;
}
// s is lowercase ASCII, so any byte slice is valid UTF-8
path.push(String::from_utf8(s[start..=i].to_vec()).unwrap());
Self::backtrack(s, i + 1, path, result);
path.pop();
}
}
fn is_palindrome(s: &[u8], mut l: usize, mut r: usize) -> bool {
while l < r {
if s[l] != s[r] {
return false;
}
l += 1;
r -= 1;
}
true
}
}