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: when start_index reaches the size of the input string, we have reached a leaf (solution).
  • get_edges: the possible next prefixes (obtained by substring start to end)
  • is_valid: the prefix must be a palindrome.
  • increment start_index by the size of the prefix.

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))
28
1import 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}
47
1using 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}
53
1function 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}
57
1#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}
54

Time 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.


TA 👨‍🏫