Partitioning A String Into Palindromes
Prereq: Backtracking
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Examples
Example 1:
Input: aab
Output:
1 [ 2 ["aa","b"], 3 ["a","a","b"] 4 ]
Try it yourself
Explanation
We try to remove prefix at each possible position and only continue if the prefix is a palindrome (since every substring has to be a palindrome to be considered a solution).
State-space Tree
We prune the tree by not branching out when the prefix is not a palindrome.
Implementation
Using Template v1.1
1function dfs(start_index, path):
2if is_leaf(start_index):
3 report(path)
4 return
5for edge in get_edges(start_index):
6 # prune if needed
7 if not is_valid(edge):
8 continue
9 path.add(edge)
10 # increment start_index
11 dfs(start_index + len(edge), path)
12 path.pop()
The edge here is a substring of s starting from start_index. We will call it prefix.
is_leaf: whenstart_indexreaches the size of the input string, we have reached a leaf (solution).get_edges: the possible nextprefixes (obtained by substringstarttoend)is_valid: theprefixmust be a palindrome.- increment
start_indexby the size of theprefix.
Solution
1from typing import List
2
3def partition(s: str) -> List[List[str]]:
4 ans = []
5
6 n = len(s)
7 def is_palindrome(word):
8 return word == word[::-1]
9
10 def dfs(start, cur_path):
11 if start == n:
12 ans.append(cur_path[:])
13 return
14
15 for end in range(start + 1, n + 1):
16 prefix = s[start: end]
17 if is_palindrome(prefix):
18 dfs(end, cur_path + [prefix])
19
20 dfs(0, [])
21 return ans
22
23if __name__ == '__main__':
24 s = input()
25 res = partition(s)
26 for row in res:
27 print(' '.join(row))
281import java.util.ArrayList;
2import java.util.List;
3import java.util.Scanner;
4
5class Solution {
6 public static boolean isPalindrome(String s) {
7 int l = 0, r = s.length() - 1;
8 while (l<r) {
9 if (s.charAt(l) != s.charAt(r))
10 return false;
11 l++;
12 r--;
13 }
14 return true;
15 }
16
17 public static void dfs(List<List<String>> ans, ArrayList<String> part, String s, int start) {
18 if (start == s.length()) {
19 List<String> li = new ArrayList<>(part);
20 ans.add(li);
21 }
22 for (int end = start; end<s.length(); end++) {
23 if (isPalindrome(s.substring(start, end + 1))) {
24 part.add(s.substring(start, end + 1));
25 dfs(ans, part, s, end + 1);
26 part.remove(part.size() - 1);
27 }
28 }
29 }
30
31 public static List<List<String>> partition(String s) {
32 List<List<String>> ans = new ArrayList<>();
33 dfs(ans, new ArrayList<String>(), s, 0);
34 return ans;
35 }
36
37 public static void main(String[] args) {
38 Scanner scanner = new Scanner(System.in);
39 String s = scanner.nextLine();
40 scanner.close();
41 List<List<String>> res = partition(s);
42 for (List<String> row : res) {
43 System.out.println(String.join(" ", row));
44 }
45 }
46}
471using System;
2using System.Collections.Generic;
3
4class Solution
5{
6 private static bool IsPalindrome(string s)
7 {
8 int l = 0, r = s.Length - 1;
9 while (l < r)
10 {
11 if (s[l] != s[r]) return false;
12 l++;
13 r--;
14 }
15 return true;
16 }
17
18 private static void Dfs(List<List<string>> ans, List<string> part, string s, int start)
19 {
20 if (start == s.Length)
21 {
22 List<string> li = new List<string>(part);
23 ans.Add(li);
24 }
25 for (int end = start; end < s.Length; end++)
26 {
27 if (IsPalindrome(s.Substring(start, end + 1 - start)))
28 {
29 part.Add(s.Substring(start, end + 1 - start));
30 Dfs(ans, part, s, end + 1);
31 part.RemoveAt(part.Count - 1);
32 }
33 }
34 }
35
36 public static List<List<string>> Partition(string s)
37 {
38 List<List<string>> ans = new List<List<string>>();
39 Dfs(ans, new List<string>(), s, 0);
40 return ans;
41 }
42
43 public static void Main()
44 {
45 string s = Console.ReadLine();
46 List<List<string>> res = Partition(s);
47 foreach (List<string> row in res)
48 {
49 Console.WriteLine(String.Join(' ', row));
50 }
51 }
52}
531function isPalindrome(word) {
2 let l = 0, r = word.length - 1;
3 while (l < r) {
4 if (word.charAt(l) != word.charAt(r)) return false;
5 l++;
6 r--;
7 }
8 return true;
9}
10
11function partition(s) {
12 const ans = [];
13 const n = s.length;
14 function dfs(start, part) {
15 if (start == n) {
16 ans.push([...part]);
17 return;
18 }
19 for (let end = start + 1; end < n + 1; end++) {
20 const prefix = s.substring(start, end);
21 if (isPalindrome(prefix)) {
22 part.push(prefix);
23 dfs(end, part);
24 part.pop();
25 }
26 }
27 }
28 dfs(0, []);
29 return ans;
30}
31
32function* main() {
33 const s = yield;
34 const res = partition(s);
35 for (const row of res) {
36 console.log(row.join(' '));
37 }
38}
39
40class EOFError extends Error {}
41{
42 const gen = main();
43 const next = (line) => gen.next(line).done && process.exit();
44 let buf = '';
45 next();
46 process.stdin.setEncoding('utf8');
47 process.stdin.on('data', (data) => {
48 const lines = (buf + data).split('\n');
49 buf = lines.pop();
50 lines.forEach(next);
51 });
52 process.stdin.on('end', () => {
53 buf && next(buf);
54 gen.throw(new EOFError());
55 });
56}
571#include <algorithm> // copy
2#include <iostream> // cin, cout
3#include <iterator> // ostream_iterator, prev
4#include <string> // getline, string
5#include <vector> // vector
6
7bool is_palindrome(std::string s) {
8 int l = 0, r = s.size() - 1;
9 while (l < r) {
10 if (s[l] != s[r]) return false;
11 l++;
12 r--;
13 }
14 return true;
15}
16
17void dfs(std::vector<std::vector<std::string>>& res, std::vector<std::string> part, std::string s, int start) {
18 if (start == s.size()) {
19 std::vector<std::string> li(part);
20 res.emplace_back(li);
21 }
22 for (int end = start; end < s.size(); end++) {
23 if (is_palindrome(s.substr(start, end + 1 - start))) {
24 part.emplace_back(s.substr(start, end + 1 - start));
25 dfs(res, part, s, end + 1);
26 part.pop_back();
27 }
28 }
29}
30
31std::vector<std::vector<std::string>> partition(std::string s) {
32 std::vector<std::vector<std::string>> res;
33 dfs(res, {}, s, 0);
34 return res;
35}
36
37template<typename T>
38void put_words(const std::vector<T>& v) {
39 if (!v.empty()) {
40 std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
41 std::cout << v.back();
42 }
43 std::cout << '\n';
44}
45
46int main() {
47 std::string s;
48 std::getline(std::cin, s);
49 std::vector<std::vector<std::string>> res = partition(s);
50 for (const std::vector<std::string>& row : res) {
51 put_words(row);
52 }
53}
54Time Complexity
Estimating time complexity of backtracking on a pruned tree is tricky because pruned branches should be excluded from the overall time complexity.
One way to estimate is to look at the operations we have done on the input.
For each letter in the input string, we can either include it as a previous string or start a new string with it.
With those two choices, the total number of operations is 2^n. We also need O(n) to check if the string is a palindrome.
In total, the complexity is O(2^n * n).
Space Complexity
The space complexity depends on the height of the tree , and the height of the state-space tree is worst-case O(n).
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.