LeetCode 131: Palindrome Partitioning Solution

Master LeetCode problem 131 (Palindrome Partitioning), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

131. Palindrome Partitioning

Medium

String Dynamic Programming Backtracking

Problem Explanation

Explanation

The problem can be solved using backtracking. We iterate through the string and at each position, we check all possible substrings starting from that position and extending to different lengths. If the substring is a palindrome, we recurse on the remaining part of the string. We keep track of the current partitioning and add it to the result when we reach the end of the string.

Algorithm:

Create a helper function that takes the input string, current starting index, current partitioning list, and the result list.
Iterate through the string starting from the current index.
Check if the substring from the current index to the end is a palindrome.
If it is a palindrome, add it to the current partitioning list and recursively call the helper function with the updated starting index.
Backtrack by removing the last element added to the partitioning list.
Repeat the process until all possible partitions are explored.

Time Complexity: The time complexity of this approach is O(n * 2^n) where n is the length of the input string. This is because for each character, we have 2 choices: either include it in a palindrome partition or not.

Space Complexity: The space complexity is O(n) for the recursion stack and O(n) for the partitioning list. Overall, the space complexity is O(n).

Solution Code

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> currentList = new ArrayList<>();
        backtrack(result, s, 0, currentList);
        return result;
    }
    
    private void backtrack(List<List<String>> result, String s, int start, List<String> currentList) {
        if (start == s.length()) {
            result.add(new ArrayList<>(currentList));
            return;
        }
        
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                currentList.add(s.substring(start, end + 1));
                backtrack(result, s, end + 1, currentList);
                currentList.remove(currentList.size() - 1);
            }
        }
    }
    
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 131 (Palindrome Partitioning)?

This page provides optimized solutions for LeetCode problem 131 (Palindrome Partitioning) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 131 (Palindrome Partitioning)?

The time complexity for LeetCode 131 (Palindrome Partitioning) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 131 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 131 in Java, C++, or Python.

Back to LeetCode Solutions