Function implementing palindrome partitioning algorithm using lookup table method.
45 {
46 int n = str.size();
47
48
49 std::vector<std::vector<int> > cuts(n, std::vector<int>(n, 0));
50
51
52 std::vector<std::vector<bool> > is_palindrome(n,
53 std::vector<bool>(n, false));
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;
79 partition++) {
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}
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4