aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning4.c
blob: 4ea0a02c722967b9895b26cd809df683f102fbde (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 1745. Palindrome Partitioning IV
#include "leetcode.h"

/*
 * given a string 's' return true if it is possible to split the string 's' into
 * three non empty palindromic substrings. otherwise, return false. a string is
 * said to be a palindrome if it is the same string when reversed
 */

bool helper(bool **is_palindrome, int k, int a, int b) {
  if (k == 1)
    return is_palindrome[a][b];
  for (int i = a; i <= b - (k - 1); i++)
    if (is_palindrome[a][i] && helper(is_palindrome, k - 1, i + 1, b))
      return true;
  return false;
}

bool checkPartitioning(char *s) {
  int n = strlen(s);
  bool **is_palindrome = (bool **)malloc(n * sizeof(bool *));
  for (int i = 0; i < n; i++)
    is_palindrome[i] = (bool *)calloc(n, sizeof(bool));
  for (int i = 0; i < n; i++)
    is_palindrome[i][i] = true;
  for (int i = 0; i < n - 1; i++)
    is_palindrome[i][i + 1] = (s[i] == s[i + 1]);
  for (int len = 3; len <= n; len++)
    for (int i = 0; i <= n - len; i++) {
      int j = i + len - 1;
      if (s[i] == s[j])
        is_palindrome[i][j] = is_palindrome[i + 1][j - 1];
    }
  bool ans = helper(is_palindrome, 3, 0, n - 1);
  for (int i = 0; i < n; i++)
    free(is_palindrome[i]);
  free(is_palindrome);
  return ans;
}

int main() {
  char *s1 = "abcbdd", *s2 = "bcbddxy";
  printf("%d\n", checkPartitioning(s1)); // expect: 1
  printf("%d\n", checkPartitioning(s2)); // expect: 0
}