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
: whenstart_index
reaches the size of the input string, we have reached a leaf (solution).get_edges
: the possible nextprefix
es (obtained by substringstart
toend
)is_valid
: theprefix
must be a palindrome.- increment
start_index
by the size of theprefix
.
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 {