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:
  [
  ["aa","b"],
  ["a","a","b"]
  ]

Try it yourself

Explanation

We try to remove the 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

function dfs(start_index, path):
if is_leaf(start_index):
   report(path)
   return
for edge in get_edges(start_index):
  # prune if needed
  if not is_valid(edge):
    continue
  path.add(edge)
  # increment start_index
  dfs(start_index + len(edge), path)
  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    n = len(s)
6
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
1"use strict";
2
3function isPalindrome(word) {
4    let l = 0;
5    let r = word.length - 1;
6    while (l < r) {
7        if (word.charAt(l) !== word.charAt(r)) return false;
8        l++;
9        r--;
10    }
11    return true;
12}
13
14function partition(s) {
15    const ans = [];
16    const n = s.length;
17    function dfs(start, part) {
18        if (start === n) {
19            ans.push([...part]);
20            return;
21        }
22        for (let end = start + 1; end < n + 1; end++) {
23            const prefix = s.substring(start, end);
24            if (isPalindrome(prefix)) {
25                part.push(prefix);
26                dfs(end, part);
27                part.pop();
28            }
29        }
30    }
31    dfs(0, []);
32    return ans;
33}
34
35function* main() {
36    const s = yield;
37    const res = partition(s);
38    for (const row of res) {
39        console.log(row.join(" "));
40    }
41}
42
43class EOFError extends Error {}
44{
45    const gen = main();
46    const next = (line) => gen.next(line).done && process.exit();
47    let buf = "";
48    next();
49    process.stdin.setEncoding("utf8");
50    process.stdin.on("data", (data) => {
51        const lines = (buf + data).split("\n");
52        buf = lines.pop();
53        lines.forEach(next);
54    });
55    process.stdin.on("end", () => {
56        buf && next(buf);
57        gen.throw(new EOFError());
58    });
59}
60
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <string>
5#include <vector>
6
7bool is_palindrome(const std::string& s) {
8    int l = 0;
9    int r = s.size() - 1;
10    while (l < r) {
11        if (s[l] != s[r]) return false;
12        l++;
13        r--;
14    }
15    return true;
16}
17
18void dfs(std::vector<std::vector<std::string>>& res, std::vector<std::string>& part, std::string& s, int start) {
19    if (start == s.size()) {
20        res.emplace_back(part);
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    std::vector<std::string> part;
34    dfs(res, part, s, 0);
35    return res;
36}
37
38template<typename T>
39void put_words(const std::vector<T>& v) {
40    if (!v.empty()) {
41        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
42        std::cout << v.back();
43    }
44    std::cout << '\n';
45}
46
47int main() {
48    std::string s;
49    std::getline(std::cin, s);
50    std::vector<std::vector<std::string>> res = partition(s);
51    for (const std::vector<std::string>& row : res) {
52        put_words(row);
53    }
54}
55
1package main
2
3import (
4    "bufio"
5    "fmt"
6    "os"
7    "strings"
8)
9
10func partition(s string) [][]string {
11    n := len(s)
12    var ans [][]string
13
14    var isPalindrome func(string) bool
15    isPalindrome = func(word string) bool {
16        for i, j := 0, len(word)-1; i < j; i, j = i+1, j-1 {
17            if word[i] != word[j] {
18                return false
19            }
20        }
21        return true
22    }
23
24    var dfs func(int, []string)
25    dfs = func(start int, curPath []string) {
26        if start == n {
27            ans = append(ans, append([]string{}, curPath...))
28            return
29        }
30        for end := start + 1; end <= n; end++ {
31            prefix := s[start:end]
32            if isPalindrome(prefix) {
33                dfs(end, append(curPath, prefix))
34            }
35        }
36    }
37
38    dfs(0, []string{})
39    return ans
40}
41
42func main() {
43    scanner := bufio.NewScanner(os.Stdin)
44    scanner.Scan()
45    s := scanner.Text()
46    res := partition(s)
47    for _, row := range res {
48        fmt.Println(strings.Join(row, " "))
49    }
50}
51

Time Complexity

Estimating the 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).

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)