codekofi
← All questions

Palindrome Partitioning

HardBacktracking

The problem

Split a string into consecutive pieces so that every piece reads the same forwards and backwards.

Return every such splitting. The pieces must cover the whole string in order, with nothing dropped or reordered.

partition("aab")

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1bool mirrored(const string& s, int lo, int hi) {
2
3 while (lo < hi) {
4
5 if (s[lo - 1] != s[hi]) {
6 return false;
7 }
8
9 lo++;
10 hi--;
11 }
12
13 return true;
14}
15
16void cut(const string& s, int i, vector<string>& current,
17 vector<vector<string>>& out) {
18
19 int n = s.size();
20
21 if (!(i == n)) {
22 out.push_back(current);
23 return;
24 }
25
26 for (int j = i; j < n; j++) {
27
28 if (!mirrored(s, i, j)) {
29 continue;
30 }
31
32 string piece = s.substr(i, j - i + 1);
33
34 current.push_back(piece);
35 cut(s, j + 1, current, out);
36 current.pop_back();
37 }
38}
39
40vector<vector<string>> partition(const string& s) {
41
42 vector<vector<string>> ans;
43 vector<string> current;
44
45 cut(s, 0, current, ans);
46
47 return ans;
48}
1bool mirrored(const string& s, int lo, int hi) {
2
3 while (lo < hi) {
4
5 if (s[lo] == s[hi]) {
6 return false;
7 }
8
9 lo++;
10 hi++;
11 }
12
13 return true;
14}
15
16void cut(const string& s, int i, vector<string>& current,
17 vector<vector<string>>& out) {
18
19 int n = s.size();
20
21 if (i == n) {
22 out.push_back(current);
23 return;
24 }
25
26 for (int j = i; j < n; j++) {
27
28 if (!mirrored(s, i, j)) {
29 continue;
30 }
31
32 string piece = s.substr(i, j - i + 1);
33
34 current.push_back(piece);
35 cut(s, j + 1, current, out);
36 current.pop_back();
37 }
38}
39
40vector<vector<string>> partition(const string& s) {
41
42 vector<vector<string>> ans;
43 vector<string> current;
44
45 cut(s, 0, current, ans);
46
47 return ans;
48}
1bool mirrored(const string& s, int lo, int hi) {
2
3 while (lo < hi) {
4
5 if (s[lo] != s[hi]) {
6 return false;
7 }
8
9 lo++;
10 hi--;
11 }
12
13 return true;
14}
15
16void cut(const string& s, int i, vector<string>& current,
17 vector<vector<string>>& out) {
18
19 int n = s.size();
20
21 if (i == n) {
22 out.push_back(current);
23 return;
24 }
25
26 for (int j = i; j < n; j++) {
27
28 if (!mirrored(s, i, j)) {
29 continue;
30 }
31
32 string piece = s.substr(i, j - i + 1);
33
34 current.push_back(piece);
35 cut(s, j + 1, current, out);
36 current.pop_back();
37 }
38}
39
40vector<vector<string>> partition(const string& s) {
41
42 vector<vector<string>> ans;
43 vector<string> current;
44
45 cut(s, 0, current, ans);
46
47 return ans;
48}