aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning.c
diff options
context:
space:
mode:
Diffstat (limited to 'palindrome_partitioning.c')
-rw-r--r--palindrome_partitioning.c56
1 files changed, 56 insertions, 0 deletions
diff --git a/palindrome_partitioning.c b/palindrome_partitioning.c
new file mode 100644
index 0000000..83bcf8d
--- /dev/null
+++ b/palindrome_partitioning.c
@@ -0,0 +1,56 @@
+// 131. Palindrome Partitioning
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * given: string 's', parition 's' such that every substring of the parition
+ * is a palindrome. return all possible palindrome paritioning of 's'.
+ */
+
+bool isPalindrome(char *s, int end) {
+ if (end < 0)
+ return false;
+ int start = 0;
+ while (end > start) {
+ if (s[start] != s[end])
+ return false;
+ start++;
+ end--;
+ }
+ return true;
+}
+
+void dfs(char *s, char ***ret, int **cols, int *retColSz, char **curr, int k) {
+ if (*s == 0) {
+ ret[*retColSz] = (char **)malloc(sizeof(char *) * k);
+ for (int i = 0; i < k; i++) {
+ ret[*retColSz][i] = (char *)malloc(strlen(curr[i]) + 1);
+ strcpy(ret[*retColSz][i], curr[i]);
+ }
+ (*cols)[(*retColSz)++] = k;
+ return;
+ }
+ int len = strlen(s);
+ for (int i = 0; i < len; i++) {
+ if (isPalindrome(s, i)) {
+ strncpy(curr[k], s, i + 1);
+ curr[k][i + 1] = '\0';
+ dfs(s + i + 1, ret, cols, retColSz, curr, k + 1);
+ }
+ }
+}
+
+char ***partition(char *s, int **returnSize, int *returnColumnSizes) {
+ *returnColumnSizes = 0;
+ if (s == NULL || !strcmp(s, ""))
+ return NULL;
+ *returnSize = (int *)malloc(sizeof(int) * 500);
+ char ***ans = (char ***)malloc(sizeof(char ***) * 500);
+ int len = strlen(s) + 1;
+ char **curr = (char **)malloc(sizeof(char *) * 500);
+ for (int i = 0; i < 500; i++)
+ curr[i] = (char *)malloc(len);
+ dfs(s, ans, returnSize, returnColumnSizes, curr, 0);
+}