101
0/320
Loading content...
Given a string s, your task is to divide it into segments where each segment reads the same forwards and backwards (i.e., each segment is a palindrome). Find all possible ways to split the string such that every resulting segment satisfies the palindrome property.
A palindrome is a sequence of characters that reads identically from left to right and right to left. For example, "radar", "level", and "a" are palindromes, while "hello" is not.
A valid segmentation is a way of dividing the entire string into one or more consecutive, non-overlapping substrings where every substring is a palindrome. The segments must cover the entire original string without any gaps or overlaps.
Return all possible valid segmentations of the string. The order of the returned segmentations does not matter, but each segmentation should list its palindromic segments in their original left-to-right order within the string.
s = "aab"[["a","a","b"],["aa","b"]]There are two valid ways to segment "aab" into palindromes: • Split into individual characters where applicable: "a" | "a" | "b" — each single character is a palindrome. • Recognize "aa" as a 2-character palindrome: "aa" | "b" — both segments are palindromes. Note that "aab" itself is not a palindrome (it reads "baa" backwards), so it cannot be a single segment.
s = "a"[["a"]]A single character is always a palindrome. The only way to segment "a" is as itself.
s = "aba"[["a","b","a"],["aba"]]There are two valid segmentations: • Split into three single-character palindromes: "a" | "b" | "a". • Keep the entire string as one segment: "aba" reads the same forwards and backwards.
Constraints