Palindrome Partitioning, Medium Leetcode
Problem is this one: https://leetcode.com/problems/palindrome-partitioning/
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]Since the author wants all the solutions, chances are DP won't work here and a brute-force seems to be a better choice. Create a function to check whether a string is a palindrome. Then, do a brute-force recursively passing in the candidates that are palindrome. Add at the end, and return. That's it. Cheers, ACC.
public class Solution
{
public IList> Partition(string s)
{
List> solution = new List>();
Partition(s, new LinkedList(), solution);
return solution;
}
private void Partition(string s,
LinkedList pal,
List> solution)
{
if (String.IsNullOrEmpty(s))
{
if (pal.Count > 0)
{
List palCopy = new List();
foreach (string p in pal)
{
palCopy.Add(p);
}
solution.Add(palCopy);
}
return;
}
string current = "";
for (int i = 0; i < s.Length; i++)
{
current += s[i].ToString();
if (IsPalindrome(current))
{
pal.AddLast(current);
Partition(s.Substring(i + 1), pal, solution);
pal.RemoveLast();
}
}
}
private bool IsPalindrome(string s)
{
if (String.IsNullOrEmpty(s)) return true;
int left = 0;
int right = s.Length - 1;
while (left < right)
{
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
}
Python is a bit shorter :)
ReplyDeleteimport functools
class Solution:
def is_palindrome(self, s):
left, right = 0, len(s)-1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
@functools.lru_cache(maxsize=None)
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
if not s:
return [[]]
return [[s[:right+1]] + p for right in range(len(s)) for p in self.partition(s[right+1:]) if self.is_palindrome(s[:right+1])]