Palindrome Partitioning

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

一个长度为n的字符串，有n-1个地方可以砍断，每个地方可断可不断两种情况，因此复杂度为 $$O(2^{n-1})$$

A string with the length of n can be partitioned at n-1 positions, and each position has two situations: partitioned or not partitioned. Since the algorithm will check every situation, the total time complexity is $$O(2^{n-1})$$

Solution

1. Define a dfs helper function
2. Loop through all the first possible partition of the passed string
3. If the partition is palindrome, then pass the remaining string to dfs helper function to check the remaining partitions

public class Solution {
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // DFS
        // define a dfs function to check palindrome recursively

        List<List<String>> result = new ArrayList<>();

        if (s == null) {
            return null;
        }

        if (s.length() == 0) {
            return result;
        }

        List<String> sub = new ArrayList<>();

        dfs(s, sub, result);

        return result;
    }

    public void dfs(String s, List<String> sub, List<List<String>> result) {

        if (s.length() == 0) {
            result.add(new ArrayList<String>(sub));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            String str = s.substring(0, i + 1);

            if (!isPalindrome(str)) {
                continue;
            }

            sub.add(str);

            String remaining = s.substring(i + 1);

            dfs(remaining, sub, result);

            sub.remove(sub.size() - 1);
        }
    }

    public boolean isPalindrome(String str) {

        char[] charArray = str.toCharArray();
        int i = 0, j = charArray.length - 1;

        while (i < j) {
            char temp = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = temp;
            i++;
            j--;
        }

        // toString() is not working, will only print out the hash code value of the object. Use String.valueOf()
        String reversedStr = String.valueOf(charArray);

        if (reversedStr.equals(str)) {
            return true;
        }

        return false;
    }
}