So I'm currently working my way through an algorithms course and this was provided as the answer for the leetcode problem "Palindrome Partitioning". I would like to be able to refactor the code so that it does not mutate the answer array and instead returns it. Preferably there would be no separate dfs function, just one recursive function called partition. I'm normally decent at this kind of thing but I'm struggling with this one:

function partition(s) {
    const ans = [];
    const n = s.length;
    function dfs(start, part) {
        if (start == n) {
            ans.push([...part]);
            return;
        }
        for (let i = start   1; i < n   1; i  ) {
            const prefix = s.substring(start, i);
            if (isPalindrome(prefix)) {
                part.push(prefix);
                dfs(i, part);
                part.pop();
            }
        }
    }
    dfs(0, []);
    return ans;
}

This is my attempt so far:

function partition(str, start) {
    const result = [];
    
    if (start == str.length) {
        result.push([str]);
    } else {
        for (let i = start   1; i < str.length; i  ) {
            const prefix = s.substring(start, i);

            if (isPalindrome(prefix)) {
                const results = partition(str, start   1);
                
                if (results.length) {
                    for (const r of results) {
                        result.push([prefix, ...r]);
                    }
                } else {
                    result.push([prefix, s.substring(i   1)]);
                }              
            }
        }
    }
    
    return result;
}

CodePudding user response：

Your attempt needs a few corrections:

• Spelling of s and str is not consistent
• The start parameter needs a default value of 0
• The recursive call is made with a wrong index. Not start 1, but i
• The base case should not place the whole string in an array. On the contrary that newly pushed array should be empty: result.push([]) or why not return [[]] immediately.
• results.length will never be zero when coming back from recursion; the else block will never execute -- it can be omitted.
• The for loop is making one iteration too few. The end condition should be i <= s.length

Here is the corrected version:

function partition(s, start=0) {
    if (start == s.length) {
        return [[]];
    }
    let result = [];
    for (let i = start   1; i <= s.length; i  ) {
        const prefix = s.slice(start, i);
        if (isPalindrome(prefix)) {
            for (const part of partition(s, i)) {
                result.push([prefix, ...part]);
            }
        }
    }
    return result;
}

Note that this makes the solution a tad slower.

CodePudding user response：

Here are Trincot's answers modified to be single entry, single exit. For anyone wondering why someone would want to do this, or for the inevitable downvoting it will get by the early return brigade, I've provided an analogy and a diagram at the bottom.

function partition(str, start = 0) {
    const result = [];
    
    if (start != str.length) {
        for (let i = start   1; i <= str.length; i  ) {
            const prefix = str.slice(start, i);
            
            if (isPalindrome(prefix)) {
                const partitions = partition(str, i);
                
                if (partitions.length == 0) {
                    result.push([prefix]);
                } else {
                    for (const part of partitions) {
                        result.push([prefix, ...part]);
                    }
                }              
            }
        }
    }
    
    return result;
}

function partition(str, start = 0) {
    const result = [];
    
    if (start != str.length) {
        for (let i = start   1; i <= str.length; i  ) {
            const prefix = str.slice(start, i);
            
            if (isPalindrome(prefix)) {
                const partitions = partition(str, i);
                
                for (const part of partitions) {
                    result.push([prefix, ...part]);
                }            
            }
        }
    }
    
    return result.length
        ? result
        : [[]];
}

function partition(str, memo = {}) {
    const result = [];

    if (str) {
        if (memo[str]) {
            result.push(...memo[str])
        } else {
            for (let i = 1; i <= str.length; i  ) {
                const prefix = str.slice(0, i);
                
                if (isPalindrome(prefix)) {
                    for (const part of partition(str.slice(i), memo)) {
                        result.push([prefix, ...part]);
                    }
                }
            }

            memo[str] = result;
        }
    }
    
    return result.length
        ? result
        : [[]];
}

function partition(str, memo = {}) {
    const result = [];

    if (str) {
        if (memo[str]) {
            result.push(...memo[str]);
        } else {
            for (let i = 1; i <= str.length; i  ) {
            
                const prefix = str.slice(0, i);
            
                if (isPalindrome(prefix)) {
                    const partitions = partition(str.slice(i), memo);

                    if (partitions.length == 0) {
                        result.push([prefix]);
                    } else {
                        for (const part of partitions) {
                            result.push([prefix, ...part]);
                        } 
                    }  
                }
            }

            memo[str] = result;
        }
    } else {
        result.push([]);
    }
    
    return result;
}

Structured Programming Hallway Analogy

Imagine you’re given a key and sent into a hallway. All along the hallway are locked doors to rooms and right at the end of the hallway is the exit.

As you come to a door along the hallway, you put your key in it and see if it opens. If it does, you enter the room. Inside the room there might be more doors. You try your key to see if any open. If they do, you walk inside and take a look around. Once you are finished in a room and there are no more doors to try you calmly walk back out to the hallway and out of the exit. This is structured programming.

Now imagine the same scenario. This time you come to a room in the hallway and the door unlocks. Great, you think, and walk straight in. Upon entering the room the door locks behind you, the floor caves in and you find yourself falling into darkness. You are being ejected from the building via a trap door. Congratulations, you have encountered an early return.

If you are working on a large codebase, the code you write will be worked on by people many years after you've departed the company. Which building would you rather explore? Which building do you want to leave for them?

Visually: