Mirror Word Splits
MediumBacktracking
Problem
A mirror word reads the same forwards and backwards ("noon", "a"). Given a string s, return every way to cut s into consecutive pieces so that every piece is a mirror word.
Each answer is the list of pieces from left to right. Return the answers in any order.
Example 1
- Input:
- s = "aab"
- Output:
- [["a", "a", "b"], ["aa", "b"]]
"aab" itself and "ab" are not mirror words, so these are the only two splits.
Example 2
- Input:
- s = "z"
- Output:
- [["z"]]
Constraints
- 1 ≤ s.length ≤ 16
- s contains only lowercase English letters.
Hint
Show the first hint
Decide the first piece, then solve the same problem for the rest of the string.
Walkthrough
How to approach it
01Clarify before coding
- Is a single letter a mirror word? Yes, so the all-single-letters split is always an answer.
- Must the pieces keep their order? Yes, inner lists are left to right; only the list of answers is unordered.
- How long is s? Up to 16, so up to 2^15 splits in the worst case ("aaaa…").
02Brute force
Try all 2^(n-1) ways to place cuts, then check every piece of each split.
Cost: O(n · 2^n), and each piece check is O(n) on its own, so O(n² · 2^n) without precomputation.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.