Back to DSA

Palindrome Partitioning

hard
Acceptance: 42%
BacktrackingStrings

Given a string, split it into segments where every segment reads the same forwards and backwards (i.e., each segment is a palindrome). Return all such ways to partition the string.

Examples

Example 1:
Input:s = "abba"
Output:[["a","b","b","a"],["a","bb","a"],["abba"]]
Example 2:
Input:s = "x"
Output:[["x"]]

Hints

Related Problems

Valid PalindromeeasyLongest Substring Without Repeating CharactersmediumGroup AnagramsmediumLongest Palindromic SubstringmediumString to Integer (atoi)medium
00:00
import java.util.*;

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

    private void backtrack(String s, int start, List<String> current, List<List<String>> result) {
        if (start == s.length()) { result.add(new ArrayList<>(current)); return; }
        for (int end = start + 1; end <= s.length(); end++) {
            String sub = s.substring(start, end);
            if (isPalindrome(sub)) {
                current.add(sub);
                backtrack(s, end, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) { if (s.charAt(l++) != s.charAt(r--)) return false; }
        return true;
    }
}
Time complexityO(n * 2^n)
Space complexityO(n)