Leetcode 131 - Palindrome Partitioning

Prompt: Given a string, find all substrings that are palindromes.

Note: A palindrome string is a string that reads the same backward as forward.

Example:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Input: s = "a"
Output: [["a"]]

Solution: A 2 part solution can be used for this problem.

First, we can find all possible substring palindromes from each position in the string. We can find all possible palindromes from a position by expanding the range of the palindrome if the start and end of the possible palindrome is equal.

Then, we can use DFS to reconstruct all the possible palindromes at all positions in the string. The runtime for the first part of the solution is O(n²) since we iterate through all letters of the string and we iterate through all other letters to find the possible palindromes. The runtime for the second part of the solution is O(m + n) where n is the number of possible palindromes and m is the number of edges between all the possible palindromes.