[LeetCode Solution 131]: Palindrome Partitioning

[LeetCode Solution 131]: Palindrome Partitioning

*********************************************************************************

Question:

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"]
]

--------------------------------------------------------------------------------------------------

Recursive Method

Strategy

We are going to use backtracking to solve this problem, the idea is if we find a palindrome  substring, we add it in a temp and go further searching, the idea is as shows in the following picture:

Java

public class Solution {

 public List<List<String>> partition(String s) {
  if (s.length() == 0 || s == null)
   return null;
  List<List<String>> res = new ArrayList<>();
  helper(res, new ArrayList<>(), 0, s);
  return res;

 }

 public void helper(List<List<String>> res, List<String> temp, int start, String s) {
  if (start == s.length()) {
   res.add(new ArrayList<>(temp));
  } else {
   for (int i = start; i < s.length(); i++) {
    if (isPalindrome(s, start, i)) {
     temp.add(s.substring(start, i+1));
     helper(res, temp, i + 1, s);
     temp.remove(temp.size() - 1);
    }

   }
  }
 }

 public boolean isPalindrome(String string, int start, int end) {
  while (start < end) {
   if (string.charAt(start++) != string.charAt(end--))
    return false;
  }
  return true;

 }
}

The Running results: