Leetcode: 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.

For example, given s = "aab",
Return

[
    ["aa","b"],
    ["a","a","b"]
]

Clarify the problem:
1. What is a palindrome?
In our previous post, we defined the palindrome as given a "A word, phrase, number, or other sequences of symbols or elements that reads the same forward or reversed, with general allowance for adjustments to punctuation and word dividers. " 

In this question, do we allow the input string contains white space, punctuation and word dividers? Do we ignore cases? E.g. Does string "Aa" a palindrome? Actually the question does not specify this, so is in the real interview. So it is very important to clarify this with the interviewer. It is an important step to show you really think about the problem. In this problem, we may assume that the input string has no punctuation, and all alphabets are lower cases. In real word, people usually ignore the cases and punctuation. For example, the link provides a list of palindrome. http://www.palindromelist.net/ 
From that, it is obviously to see that palindrome usually ignores cases and punctuation. Therefore, in this question, we shall do a pre-process that removes all punctuation and converts all upper cases characters to lower cases.  

2. What is a substring in a string?
A substring could be either the string itself or its substrings. For instance, for string "run", its sbustring could be: 
r
u
n
ru
un
run

3. What is a partition of a string?
A partition of a string is to partition a string into its substrings. For instance, the partition of a string "run" will be
run
ru, n
r, un
r, u, n

4. What is the basic data structure used in this problem?
The next question is how to store the substrings which are palindrome? We could simply use a ArrayList, of each element stores the substring which is a palindrome for the specified string. For example, for the string "aab", we returns 
["aa", "b"] and ["a", "a", "b"]

Naive Solution:
According to the analysis above, now you may get the basic idea of the solution. We could find all partitions of the string and check if it is palindrom. For instance, for the string "aab" we first check is the first partition "aab" a palindrome? Obviously it is not. So we keep searching its sub-partitioning. If we only partition once, the partition of the string "aab" could be "aa", "b" or "a", "ab". For a given partition, we check if every substring of the partition is a palindrome. If yes, we store the substrings into a ArrayList. 

So the native solution has two steps.  We first find all partitions of a given string, then we check every substring in a partition is a palindrome. 

Recursive Solution:

public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        ArrayList<String> levelList = new ArrayList<String>();
        
        partitionHelper(s, result, levelList);
        
        return result;
    }
    
    private void partitionHelper(String s, ArrayList<ArrayList<String>> result, ArrayList<String> levelList) {
        if (s.isEmpty()) {
            result.add(new ArrayList<String>(levelList));
            //levelList.clear();
            return;
        }
        
        for (int i = 1; i <= s.length(); i++) {
            if (isPalin(s.substring(0, i))) {
                levelList.add(s.substring(0, i));
                partitionHelper(s.substring(i), result, levelList);
                levelList.remove(levelList.size() - 1);
            }
        }
    }
    
    private boolean isPalin(String s) {
        if (s.isEmpty()) return true;
        
        int len = s.length();
        int start = 0;
        int end = len - 1;
        
        while (start < len) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Discussion:
Note that in line 14 and 22, which are the most tricky parts in the code. 

Summary:
The problem is tricky however not too hard. Do understand the ideas of partitioning the string. It is commonly used in many other string partitioning problem.

Update on 10/28/14:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return result;
        }
        List<String> curr = new ArrayList<String>();
        partitionHelper(0, s, curr, result);
        
        return result;
    }
    
    private void partitionHelper(int start, String s, List<String> curr, List<List<String>> result) {
        if (start >= s.length()) {
            result.add(new ArrayList<String>(curr));
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            if (isPalin(start, i, s)) {
                curr.add(s.substring(start, i + 1));
                partitionHelper(i + 1, s, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
    
    private boolean isPalin(int start, int end, String str) {
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}