Backtracking - 131. Split palindrome string

1 Title Description

131. Split palindrome string
     Give you a string s, Would you please s Split into some substrings , So that each substring is Palindrome string . return s All possible segmentation schemes .

Palindrome string It's the same string read forward and backward .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/palindrome-partitioning

2 Title Example

Example 1：
Input ：s = “aab”
Output ：[[“a”,“a”,“b”],[“aa”,“b”]]

Example 2：
Input ：s = “a”
Output ：[[“a”]]

3 Topic tips

1 <= s.length <= 16
s It's only made up of lowercase letters

4 Ideas

Method 1 ： to flash back + Dynamic programming preprocessing
Because you need to find the string s All segmentation schemes , So we consider using search ＋ The backtracking method enumerates all possible segmentation methods and makes judgments .
Let's say we currently find the... Of the string i Characters , And s[0…i-1] All characters of the position have been divided into several palindrome strings , And the segmentation result is put into the answer array ans in , Then we need to enumerate the right boundary of the next palindrome string j, bring s[i…j] It's a palindrome string .
therefore , We can i Start , Enumerate from small to large j. For the current enumeration j value , We use the double pointer method to judge s[i…j] Whether it is palindrome string : If s[i…j] It's a palindrome string , Then add it to the answer array ans in , And j＋1 As new à Go to the next level of search , And back in the future will s[i…j] from ans Remove .
If we have searched the last character of the string , So we found — A segmentation method that meets the requirements .
Complexity analysis
Time complexity :o(n 2²), among n Is string s The length of . In the worst case ,s contain n Two identical characters , So its arbitrary — All kinds of division methods meet the requirements . And the length is n The number of partition schemes of the string is 2^n-1= o(2²), Each division method requires O(n) Find the corresponding division result and put it into the answer , So the total time complexity is o(n·2²). Although dynamic programming preprocessing needs o(n²) Time for , But in a gradual sense, it is less than O(n2²), So we can ignore .
· Spatial complexity :O(n²), The space occupied by returning the answer is not calculated here . Array f The space to be used is O(n2), And in the process of backtracking , We need to use O(n) Stack space and O(n) The space used to store the current string segmentation method . because O(n) Less than... In a progressive sense o(n²), So the space complexity is zero O(n²).

Method 2 ： to flash back + Memory search
The dynamic programming preprocessing in method 1 calculates arbitrary s[i…j] Whether it is palindrome string , We can also put this — Step change to memory search .
Complexity analysis

• Time complexity :O(n ﹒ 2²), among n Is string s The length of , Same as method one .
• Spatial complexity :o(n²), With the method — identical .

5 My answer

Method 1 ： to flash back + Dynamic programming preprocessing

class Solution {
    
    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
    
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
    
            Arrays.fill(f[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
    
            for (int j = i + 1; j < n; ++j) {
    
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
    
        if (i == n) {
    
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
    
            if (f[i][j]) {
    
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}

Method 2 ： to flash back + Memory search

class Solution {
    
    int[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
    
        n = s.length();
        f = new int[n][n];

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
    
        if (i == n) {
    
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
    
            if (isPalindrome(s, i, j) == 1) {
    
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    //  In memory search ,f[i][j] = 0  Indicates no search ,1  Indicates a palindrome string ,-1  Indicates that it is not a palindrome string 
    public int isPalindrome(String s, int i, int j) {
    
        if (f[i][j] != 0) {
    
            return f[i][j];
        }
        if (i >= j) {
    
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
    
            f[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
    
            f[i][j] = -1;
        }
        return f[i][j];
    }
}