Description

Given a strings, partition_s_such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s ="aab", return:

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

Solution

一道典型的backtrack题

public class Solution {
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> ret = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return ret;
        }

        List<String> list = new ArrayList<String>();
        partitionHelper(s, list, ret, 0);
        return ret;
    }

    private void partitionHelper(String s, List<String> list, List<List<String>> ret, int index) {
        if (index == s.length()) {
            ret.add(new ArrayList<String>(list));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                list.add(s.substring(index, i + 1));
                partitionHelper(s, list, ret, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        if (start >= end) {
            return true;
        }

        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }

        return isPalindrome(s, start + 1, end - 1);
    }
}