King Of Interviews

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.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

Try this Problem on your own or check similar problems:

Solution:

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

    private void helper(String s, int start, List<String> currentList, List<List<String>> result){
        if(s.length() == start){
          result.add(new ArrayList<>(currentList));
          return;
        }

        for(int i = start; i < s.length(); ++i){
            String subString = s.substring(start, i+1);
            if(isPalindrome(subString)){
                currentList.add(subString);
                helper(s, i + 1, currentList, result);
                currentList.remove(currentList.size()-1);
            }
        }
    }

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

Time/Space Complexity:

Time Complexity: O(n*2^n)
Space Complexity: O(n)

Explanation:

Another backtracking problem, where we use the same approach/template we did for all backtracking problems (e.g. Combinations ). The bulk logic is again in the helper function, where we check if current substring is palindrome (with the isPalindrome function which just iterates over the string simultaneously from left and right and checks for equality which is the definition of palindrome - reads the same from left to right and right to left). If the current substring is a palindrome, we add it to the current partition list currentList and call the helper function to search for all remaining partitions in the rest of the string. Recursion stack is n (length of the string) deep so that’s our space complexity, the time complexity is O(n\*2^n) as always we have the n multiplier (for checking whether the string is a palindrome and also coping the currentList to the result, worst case every character is palindrome by itself so we will have n lists), and for the recursion we have in total 2^n nodes (the reasining behind this is that there are in total 2^n different partitions of any string). As always after the helper function call, we backtrack and remove our current candidate from our partition list.

Palindrome Partitioning