Palindrome Partitioning

Medium

The problem

Cut the string s into pieces so that every piece reads the same forwards and backwards. Return all the ways to do this, each as a list of pieces in the original order. The ways can be in any order.

Example 1
Input: s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]
"aab" itself is not a palindrome, and "ab" is not either, so those cuts are not allowed.
Example 2
Input: s = "a"
Output: [["a"]]

Limits

1 ≤ s.length ≤ 12
s has only lowercase English letters
The order of the ways does not matter

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

At each position decide where the next piece ends — and only keep pieces that are palindromes.

The idea

DFS(start): for each end ≥ start, if s[start..end] is a palindrome add it and recurse from end+1; record when start reaches the end.

Target: O(n · 2^n) time

Go function shape

func partition(s string) [][]string

Reference solution

Tested with go test. Try it yourself first, then compare.

// Partition: at each position choose where the next piece ends, and only continue with pieces that are palindromes.
func Partition(s string) [][]string {
	isPal := func(l, r int) bool {
		for l < r {
			if s[l] != s[r] {
				return false
			}
			l++
			r--
		}
		return true
	}
	out := [][]string{}
	var path []string
	var dfs func(start int)
	dfs = func(start int) {
		if start == len(s) {
			out = append(out, append([]string{}, path...))
			return
		}
		for end := start; end < len(s); end++ {
			if isPal(start, end) {
				path = append(path, s[start:end+1])
				dfs(end + 1)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return out
}

Read the lesson: Backtracking