Palindrome Partitioning

2 min read
LC-Medium
Backtracking

Oct 21, 2022

3 years ago

LeetCode

Solution

Backtracking solution
Start from index i (initially 0), and for each index, generate all possible substrings from index i to index len(s) - 1
- If current substring is a palindrome, add substring to part and recur further to next index
- If current substring is not a palindrome, don't do anything. This is because all our substrings need to be a palindrome.
If the above point is confusing:
- For the string 'aab', first call is to dfs(0)
  - Check all characters from i (which is 0) to len(s)
    - i.e. we check if 'a', 'a', and 'b' are palindromes
      - When checking if 'a' is a palindrome, it is, and then we recur to the remaning of the substring
        I.e. we check if the second 'a' is a palindrome
        It is, so we recur further. Current path is ['a', 'a']. We no w check if 'b' is a palindrome. It is. We add it to our path. And now we've reached the end ['a', 'a', 'b'] is one of our answers.
        
        ... and we also check if 'ab' is a palindrome -> it isn't. Return
    - We also check whether 'aa' is a palindrome
      - It is. During the next recursive call:
        We check if the remaining string 'b' is a palindrome- it is
        Append the current substring b to answer- we'll have ['aa', 'b'] as our answer- these are both individually palindromes.
    - We also check whether 'aab' is a palindrome
      - It is not- we stop here.

Time	Space	Explanation
`O(n * 2^n)`	`O(n)`	O(n) for checking if string is a palindrome, and O(2 ^ n) because there are O(2^n) nodes in the subtree above

def is_palindrome(self, s, l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True def partition(self, s: str) -> List[List[str]]: ans, part = [], [] def dfs(i): if i >= len(s): ans.append(part[:]) return for j in range(i, len(s)): if self.is_palindrome(s, i, j): part.append(s[i:j+1]) dfs(j + 1) part.pop() dfs(0) return ans