Palindrome Partitioning Using Backtracking in DSA Typescript - Build from Scratch

Palindrome Partitioning Using Backtracking

📖 Scenario: Imagine you have a word, and you want to split it into parts where each part reads the same forwards and backwards. This is called palindrome partitioning. For example, the word "noon" can be split into ["n", "oo", "n"] or ["noon"].

🎯 Goal: You will build a program that finds all the ways to split a given word into palindrome parts using backtracking. This helps understand how to explore all possible splits and check palindrome conditions step-by-step.

📋 What You'll Learn

Create a string variable with a specific word

Create a helper function to check if a substring is a palindrome

Use backtracking to find all palindrome partitions

Print all palindrome partitions as arrays of strings

💡 Why This Matters

🌍 Real World

Palindrome partitioning helps in text processing tasks like DNA sequence analysis, data compression, and pattern recognition where symmetrical patterns matter.

💼 Career

Understanding backtracking and palindrome checks is useful for software engineers working on algorithms, coding interviews, and solving complex recursive problems.

1

Create the input string

Create a string variable called input and set it to the value "aab".

DSA Typescript

# Create a string variable called input and set it to "aab"
// Your code here

Hint

Use const input: string = "aab"; to create the string.

2

Create a palindrome check function

Create a function called isPalindrome that takes a string s and returns true if s is a palindrome, otherwise false. Use a simple loop to compare characters from start and end.

DSA Typescript

const input: string = "aab";
// Create function isPalindrome(s: string): boolean
// Your code here

Hint

Use two pointers from start and end to check characters. Return false if mismatch found, else true.

3

Implement backtracking to find palindrome partitions

Create a function called backtrack that takes start: number, path: string[], and result: string[][]. Use a for loop from start to input.length. For each substring from start to i + 1, check if it is a palindrome using isPalindrome. If yes, add substring to path, call backtrack recursively with i + 1, then remove last element from path. If start equals input.length, push a copy of path to result.

DSA Typescript

const input: string = "aab";

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Create function backtrack(start: number, path: string[], result: string[][])
// Your code here

Hint

Use recursion and loop to explore all substring splits. Add palindrome substrings to path and backtrack.

4

Print all palindrome partitions

Create an empty array called result of type string[][]. Call backtrack with 0, an empty array, and result. Then print result using console.log(result).

DSA Typescript

const input: string = "aab";

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

function backtrack(start: number, path: string[], result: string[][]): void {
    if (start === input.length) {
        result.push([...path]);
        return;
    }
    for (let i = start; i < input.length; i++) {
        const substring = input.substring(start, i + 1);
        if (isPalindrome(substring)) {
            path.push(substring);
            backtrack(i + 1, path, result);
            path.pop();
        }
    }
}

// Create result array and call backtrack, then print result
// Your code here

Hint

Initialize an empty array, call backtrack starting at 0, then print the result array.