131. Palindrome Partitioning

LeetCode 131. Palindrome Partitioning****

Description

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16

• s contains only lowercase English letters.

Tags

Backtracking

Solution

Use the DFS template. Every time we examine the input string from the very first character to the whole string (Note: the index for traversal is from 1 to n, including n) if it is a palindrome. If it is, we append this substring to path , then DFS the remaining string. The boundary contiditon is the input string is empty, and we append path to the result 2D string slice.

Complexity

• Time complexity: $O(n\times2^n)$, the worst case happens when the input string is the same character repeated n times. Thus it has $2^n$ possible partitioning of s.

• Space complexity: $O(n^2)$, needs $O(n)$ for path to store temporary result and stack space $O(n)$ for recursion.

Code

func partition(s string) [][]string {
	var ans [][]string
	dfs(&ans, s, []string{})
	return ans
}

func dfs(ans *[][]string, s string, path []string) {
	if len(s) == 0 {
		temp := make([]string, len(path))
		copy(temp, path)
		*ans = append(*ans, temp)
	}
	for i := 1; i <= len(s); i++ { // note: i is in [1,n]
		if isPalindrome(s[:i]) {
			path = append(path, s[:i])
			dfs(ans, s[i:], path)
			path = path[:len(path)-1]
		}
	}
}

func isPalindrome(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}