leetcode 132. Palindrome Partitioning II 回文子串 + 深度优先遍历DFS(超时) + 动态规划DP + 这道题需要认真学习

拼搏现实的明天。 2022-06-08 05:36 29阅读 0赞

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,  
Return 1 since the palindrome partitioning \[“aa”,”b”\] could be produced using 1 cut.

本体是考察数量最少的回文子串，假如使用上一道题[leetcode 131. Palindrome Partitioning 按照index做DFS][leetcode 131. Palindrome Partitioning _index_DFS] 来做，但是会超时。

\*对于一个长度为n的字符串，设DP\[i\]\[j\]表示第i个字符到第j个字符是否构成回文，若是，则DP\[i\]\[j\]=1;若否，则DP\[i\]\[j\]=0;如此，根据回文的约束条件（对称性），DP\[i\]\[j\]构成回文需满足：  
1）输入字符串s\[i\]==s\[j\],对称性；  
2）条件1满足并不能保证i到j构成回文，还须：（j-i）<=1或者DP\[i+1\]\[j-1\]=1；即，i、j相邻或者i=j，也就是相邻字符相等构成回文或者字符自身构成回文，如果i、j不相邻或者相等，i到j构成回文的前提就是DP\[i+1\]\[j-1\]=1.

所以状态转移方程：DP\[i\]\[j\]=(s\[i\]==s\[j\]&&(j-i<=1||DP\[i+1\]\[j-1\]==1))。

int\[\] cut=new int\[s.length()+1\],cut\[i\]表示第i个字符到最后一个字符所构成的子串的最小分割次数，这里的i有约束条件，就是第i个位置必须是可进行回文分割的，即DP\[i\]\[j\]==1 (j>=i&&j

/*
     * 对于一个长度为n的字符串，设DP[i][j]表示第i个字符到第j个字符是否构成回文，若是，
     * 则DP[i][j]=1;若否，则DP[i][j]=0;如此，根据回文的约束条件（对称性），DP[i][j]构成回文需满足：
     * 1、输入字符串s[i]==s[j],对称性；
     * 2、条件1满足并不能保证i到j构成回文，还须：（j-i）<=1或者DP[i+1][j-1]=1；
     * 即，i、j相邻或者i=j，也就是相邻字符相等构成回文或者字符自身构成回文，如果i、j不相邻或者相等，i到j构成回文的前提就是DP[i+1][j-1]=1.
     * 
     * 所以状态转移方程：DP[i][j]=(s[i]==s[j]&&(j-i<=1||DP[i+1][j-1]==1))。
     * 
     * int[] cut=new int[s.length()+1],cut[i]表示第i个字符到最后一个字符所构成的子串的最小分割次数，
     * 这里的i有约束条件，就是第i个位置必须是可进行回文分割的，即DP[i][j]==1 (j>=i&&j<s.length()),
     * 
     * http://blog.csdn.net/jin_kwok/article/details/51423222 
     * 需要好好的想一下
     * */
    public class Solution 
    {
        public int minCut(String s)
        {
            if(s==null)
                return 0;
            int [][]dp = new int[s.length()][s.length()];
            int []minNum = new int[s.length()+1];   
            for(int i=s.length()-1;i>=0;i--)
            {
        
                minNum[i] = Integer.MAX_VALUE;
                for(int j=i;j<s.length();j++)
                {
        
                    if(s.charAt(i)==s.charAt(j) && (i==j || j-i==1 || dp[i+1][j-1]==1))
                    {
        
                        dp[i][j]=1;
                        minNum[i] = Math.min(minNum[i], 1+minNum[j+1]);         
                    }
                }
            }
            return minNum[0]-1;
        }
    }

下面是C++的做法， 就是一个DP动态规划的问题，这道题需要学习的地方就是如何写DP的循环。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int minCut(string s)
        {
            int n = s.length();
            vector<vector<bool>> dp(n, vector<bool>(n, false));
            vector<int> mincut(n+1,INT_MAX);
            mincut[n] = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = i; j < n; j++)
                {
                    if (s[i] == s[j] && (i == j || j - i == 1 || dp[i + 1][j - 1] == true))
                    {
                        dp[i][j] = true;
                        mincut[i] = min(mincut[i], mincut[j + 1] + 1);
                    }
                }
            }
            return mincut[0] - 1;
        }
    };

[leetcode 131. Palindrome Partitioning _index_DFS]: http://blog.csdn.net/jackzhang_123/article/details/78002862