Function implementing palindrome partitioning algorithm using lookup table method.
45 {
47
48
50
51
54
55
56 for (int i = 0; i < n; i++) {
57 is_palindrome[i][i] = true;
58 cuts[i][i] = 0;
59 }
60
61 for (int len = 2; len <= n; len++) {
62 for (int start_index = 0; start_index < n - len + 1; start_index++) {
63 int end_index = start_index + len - 1;
64
65 if (len == 2) {
66 is_palindrome[start_index][end_index] =
67 (str[start_index] == str[end_index]);
68 } else {
69 is_palindrome[start_index][end_index] =
70 (str[start_index] == str[end_index]) &&
71 is_palindrome[start_index + 1][end_index - 1];
72 }
73
74 if (is_palindrome[start_index][end_index]) {
75 cuts[start_index][end_index] = 0;
76 } else {
77 cuts[start_index][end_index] = INT_MAX;
78 for (
int partition = start_index;
partition <= end_index - 1;
80 cuts[start_index][end_index] =
81 std::min(cuts[start_index][end_index],
82 cuts[start_index][partition] +
83 cuts[partition + 1][end_index] + 1);
84 }
85 }
86 }
87 }
88
89 return cuts[0][n - 1];
90}