Java: Palindrome Partitioning

Thought Process

The problem requires partitioning a string into all possible palindromic substrings. We use backtracking to explore all valid partitions. For each position in the string, we check if the substring from the current position to a chosen endpoint is a palindrome. If it is, we add it to the current partition and recursively explore further. Once we reach the end of the string, we add the valid partition to the result. This ensures we explore all possible ways to partition the string into palindromic substrings. 

class Solution {
    
    public void backTrack(List<List<String>> ans, List<String> tmp, String str, int start){

        if(start>=str.length())
            ans.add(new ArrayList<>(tmp));

        for(int i=start;i<str.length();i++){

            if(isPalindrome(str,start,i)){
                tmp.add(str.substring(start,i+1));
                backTrack(ans,tmp,str,i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
    public List<List<String>> partition(String str) {
        
        List<List<String>> ans = new ArrayList<>();
        List<String> tmp = new ArrayList<>();

        backTrack(ans,tmp,str,0);
        return ans;
    }

    public boolean isPalindrome(String str, int i, int j){

        int left = i;
        int right = j;

        while(left<right){

            if(str.charAt(left)==str.charAt(right)){
                left++;
                right--;
            }
            else
                return false;     
        }
        return true;
    }
}

Code Complexity

Time Complexity: O(n * 2^n)

The algorithm explores all possible partitions of the string, resulting in exponential time complexity. Each partition check takes O(n) time.

Space Complexity: O(n)

The algorithm uses recursion, which consumes stack space proportional to the length of the string.

Code copied!