Palindromic Decomposition Of A String

Problem

Find all palindromic decompositions of a given string s.

A palindromic decomposition of string is a decomposition of the string into substrings, such that all those substrings are valid palindromes.

Example

{
"s": "abracadabra"
}

Output:

["a|b|r|a|c|ada|b|r|a", "a|b|r|aca|d|a|b|r|a", "a|b|r|a|c|a|d|a|b|r|a"]

Solution

function is_palindrome(s, l, r) {
    while (l < r) {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}

function dfs(decompositions_container, s, pos, cur_decomposition) {
    // If we have reached the end, add the string.
    let n = s.length;
    if (pos == n) {
        decompositions_container.push(cur_decomposition);
        return decompositions_container;
    }
    // Try to add s[pos, i] if it a palindrome.
    for (let i = pos; i < n; i++) {
        if (is_palindrome(s, pos, i)) {
            if (pos == 0) {
                // We are adding s[0, i] so do not put '|' before it.
                dfs(decompositions_container, s, i + 1,
                    s.substr(pos, i - pos + 1, n));
            }
            else {
                dfs(decompositions_container, s, i + 1,
                    cur_decomposition + '|' + s.substr(pos, i - pos + 1));
            }
        }
    }
}

function generate_palindromic_decompositions(s) {

    let decompositions_container = [];

    dfs(decompositions_container, s, 0, "");
    
    return decompositions_container;
}

generate_palindromic_decompositions('abracadabra');

Time and Space Complexity

Time: O(2^(n-1) * n).
Auxiliary space: O(2^(n-1) * n).
Total space: O(2^(n-1) * n).