Palindrome Partitioning
Updated
Problem statement
Return every way to split s into nonempty contiguous substrings so that every substring is a palindrome. A palindrome reads the same from left to right and right to left.
Each partition must cover the entire string without changing its character order. Return partitions in the order obtained by trying the shortest next piece first at every step. For the empty string, return one empty partition: [[]].
Function
partitionPalindromes(s: String) → String[][]Examples
Example 1
s = "aab"return = [["a","a","b"],["aa","b"]]The valid partitions are ["a","a","b"] and ["aa","b"]. The first one chooses the shorter first piece.
Example 2
s = "aba"return = [["a","b","a"],["aba"]]The valid partitions are ["a","b","a"] and ["aba"]. Neither "ab" nor "ba" is a palindrome.
Example 3
s = ""return = [[]]The empty partition covers the empty string, so the result contains exactly one empty partition.
Constraints
- 0 <= s.length <= 10.
- Every character is a lowercase English letter.
More London Stock Exchange interview questions
- Implement a Queue Using an ArrayPHONE SCREEN · Seen Feb 2020
- Lowest Common Ancestor in a Binary TreePHONE SCREEN · Seen Feb 2020
- Two SumPHONE SCREEN · Seen Feb 2020
- Two Sum in a Sorted ArrayPHONE SCREEN · Seen Feb 2020
- Group Anagram StringsONSITE INTERVIEW · Seen Apr 2020
- Implement Key Equality and HashingONSITE INTERVIEW · Seen Apr 2020
Similar questions at other companies
- Generate One-Two Strings with Sum NGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Word Break IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word Break IIWex · PHONE SCREEN
- Word Break IIInMobi · PHONE SCREENInMobi interview questions
- Word Break IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Word Break II: All SentencesMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- All Palindrome PartitionsExpedia · OAExpedia interview questions
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- Longest Palindromic SubstringSiemens · PHONE SCREEN
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions