131 Palindrome Partitioning

131. Palindrome Partitioning

1. Question

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

Return all possible palindrome partitioning ofs.

For example, givens="aab", Return

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

2. Implementation

(1) Backtracking

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> palindromes = new ArrayList<>();
        getPartitions(0, s, palindromes, res);
        return res;
    }

    public void getPartitions(int index, String s, List<String> palindromes, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(palindromes));
            return;
        }

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

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

3. Time & Space Complexity

Backtracking: 时间复杂度O(n * 2^n), 空间复杂度O(2^n)