This is the 24th day of my participation in the wenwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

135. Palindrome-partitioning

The label

• string
• medium

The title

Leetcode portal

Let’s just open leetCode.

Given a string s, please split s into substrings so that each substring is a palindrome string. Returns all possible segmentation schemes for S.

A palindrome string is a string that is read forward and backward identically.

Example 1

Input: s = "aab" output: [["a","a","b"] [" AA ","b"]Copy the code

Example 2

Input: s = "a" output: [["a"]]Copy the code

The basic idea

The first step is to disassemble the problem

• First we have to have a way to determine whether it’s palindrome, inputstrreturntrue/false.
• Because our output is enumerating all the shards, it comes naturallyDFS + backIf this is not ripe please move onThis articleI told you the basics of this.

Because it is to find all possible segmentation, in fact, similar to full permutation, this kind of problem is DFS + backtracking, in fact, as how to cut this long string, each cut should cut a palindrome string, until the end. To find all the states, you need to go back and think about whether there is a way to go without cutting. That is, go back to where you were before the choice, look at another choice, go to the next iteration, try another possibility of segmentation. Finally, output all the legal solution sets.

The basic steps of DFS are

• Cur pointer has gone to the tail, indicating that it is finished, resulting in res
• Iterate over the following characters to determine where to cut next (meet palindromes)
  • Add it to the set of partial solutions, recursively cut down (the left side is already a palindrome string), and backtrack to find other cuts
  • The current knife is not a palindrome, skip this selection, I go down

Writing implement

var partition = function(s) {
    const res = []
    // Subproblem 1: double pointer judgment palindrome, from both ends to the middle
    const isPalindrome = (left, right) = > {
        while (left < right) {
            if(s[left] ! == s[right]) {return false
            }
            left++;
            right--;
        }
        return true
    }
    const dfs = (subArr, cur) = > {
        // the cur pointer has reached the end of the pointer, indicating that it is finished
        if (cur === s.length) {
            // res is an array
            res.push(subArr.slice());
            return;
        }
        // Iterate over the following situation
        for (let i = cur; i < s.length; i++) {
            [cur, I] is a palindrome
            if (isPalindrome(cur, i)) {
                // The correct callback substring is pushed
                subArr.push(s.substring(cur, i + 1));
                // Recursively, find the next selection after the current substring
                dfs(subArr, i + 1);
                // Backtrack to find another solution
                subArr.pop();
            }
        }
    }

    dfs([], 0)
    return res
};

let s = "aab"
console.log(partition(s))
["a","a","b"],[" AA ","b"]]
Copy the code

Something today, going to play football, to a question ha.

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference