131. Palindrome Partitioning
- Total Accepted: 77657
- Total Submissions: 260955
- Difficulty: Medium
- Contributors: Admin
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab"
,
Return
[ ["aa","b"], ["a","a","b"] ]
Code
class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ res = [] self.recur(0, s, [], res) return res def recur(self, cur_idx, s, splits, res): if cur_idx == len(s): res.append(list(splits)) return for i in xrange(cur_idx + 1, len(s)+1): if self.isPalindrome(s[cur_idx:i]): splits.append(s[cur_idx:i]) self.recur(i, s, splits, res) splits.pop() def isPalindrome(self, ss): return ss == ss[::-1]
Idea
You progressively try every split position in the string. Check whether substring between the last split position to current split position is palindrome. If so, recursively try the rest of split positions, with the current substring being added to splits
.
Reference: https://discuss.leetcode.com/topic/10955/clean-c-backtracking-solution