Split palindromes, difficulty: Medium. The original problem is here.

Topic describes

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

Tip:

• 1 <= s.length <= 16
• sContains only lowercase English letters

Thought analysis

Grasp the key word palindrome, return all the segmentation scheme, you know that the problem and DFS backtracking is indispensable. Each substring must be a palindrome string. Please find all possible shards. Starting from the root node S, enumerate all character combinations that can be cut off. If the cut combination is not a palindrome string, it will not continue; if it is a palindrome string, it will continue to be cut based on the remaining substrings after the cut. So you can draw an N-fork tree, where one path from the root to the leaf is a set of seeds, and you can go back through the tree and get all the solutions. In addition, how to quickly determine whether it is a palindrome string? LeetCode 5. The longest loop substring is combined with dynamic programming and state transition equation is derived to assist the solution.

Code reference LeetCode@ stupid pig blasting group problem solving

AC code

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const res = [];
    const dp = new Array(s.length);
    for (let i = 0; i < dp.length; i++) {
        dp[i] = new Array(s.length);
    }

    for (let j = 0; j < s.length; j++) {
        for (let i = 0; i <= j; i++) {
            if (i == j) {
                dp[i][j] = true;
            } else if (j - i == 1 && s[i] == s[j]) {
                dp[i][j] = true;
            } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
            } else {
                dp[i][j] = false;
            }
        }
    }

    function dfs (temp, start) {
        if (start === s.length) {
            res.push(temp.slice());
            return;
        }
        for (let i = start; i < s.length; i++) {
            if (dp[start][i]) {
                temp.push(s.substring(start, i +1));
                dfs(temp, i + 1);
                temp.pop();
            }
        }
    }

    dfs([], 0);
    return res;
};

Copy the code

conclusion

答 案 :

• 132. Split palindrome string II

Techniques used

• Define the DP subproblem:dp[i][j]From:i 到 jWhether the substring of.
  • dp[i][j]To be true, list all the cases:
    1. i == jWhen, the substring has only one character, affirming palindrome
    2. j-i == 1When, the substring consists of two characters, which must be the sames[i] == s[j]
    3. j-i > 1, the substring consists of more than two characters,s[i] == s[j]And,dp[i+1][j-1]=trueThat is, any substring that removes the first and last characters is also a callback substring.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign