607. Mirror Cuts
A jeweller wants to cut a string of beads, written as the lowercase string s, into consecutive pieces so that every piece reads the same forwards and backwards. A piece of a single bead always qualifies.
Return every way to cut s into such pieces. Each way is an array of the pieces in the order they appear in s, and all ways must be listed exactly once. The ways may be returned in any order.
Precompute which substrings are palindromes so each candidate piece is tested in constant time.
Example 1
- Input:
- s = "noon"
- Output:
- [["n","o","o","n"],["n","oo","n"],["noon"]]
- Explanation:
Three cuts work:
n|o|o|n,n|oo|nandnoon.
Example 2
- Input:
- s = "xyz"
- Output:
- [["x","y","z"]]
- Explanation:
No two beads match, so the only cut is into single beads:
x|y|z.
Example 3
- Input:
- s = "aab"
- Output:
- [["a","a","b"],["aa","b"]]
- Explanation:
Two cuts exist:
a|a|bandaa|b.
Constraints
- 1 ≤
s.length≤ 8 sconsists of lowercase English letters.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n * 2^n)
- Space
- O(n^2)