Palindrome Partitioning

Medium

LeetCode ↗

Strings Dynamic Programming Recursion Backtracking Dynamic Programming

Problem

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 is a string that reads the same forward and backward.

Constraints

1 <= s.length <= 16
s contains only lowercase English letters

Examples

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

There are two valid partitions: split into individual characters ['a','a','b'], or combine the first two characters into the palindrome 'aa' plus 'b'.

Input: s = "a"

Output: [["a"]]

A single character is always a palindrome, so the only partition is the string itself.

Loading...

Loading Python...