Facebook Pixel

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 {