132. 分割回文串 II

谁借莪１个温暖的怀抱￠ 2022-12-07 11:49 126阅读 0赞

# 题目： #

[132. 分割回文串 II][132. _ II]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：动态规划 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

# 代码：动态规划 #

public class code132 { 
    
        public static int minCut(String s) { 
            int len = s.length();
            if(len < 2)
            { 
                return 0;
            }
    
            // dp[i]：表示前缀子串 s[0:i] 分割成若干个回文子串所需要最小分割次数。
            int dp[] = new int[len];
            for(int i = 0; i < len; i++)
            { 
                dp[i] = i;
            }
            for(int i = 1; i < len; i++)
            { 
                // 如果 s[0:i] 本身就是一个回文串，那么不用分割，即 dp[i] = 0 ，这是首先可以判断的，否则就需要去遍历；
                if(isPalindrome(s, 0, i))
                { 
                    dp[i] = 0;
                    continue;
                }
                // 接下来枚举可能分割的位置：即如果 s[0:i] 本身不是一个回文串，就尝试分割，枚举分割的边界 j。
                // 当 j == i 成立的时候，s[i] 就一个字符，一定是回文
                // 因此，枚举到 i - 1 即可
                for(int j = 0; j < i; j++)
                { 
                    // 如果 s[j + 1, i] 是回文串，则 dp[i] 就是在 dp[j] 的基础上多一个分割。
                    // 于是枚举 j 所有可能的位置，取所有 dp[j] 中最小的再加 1 ，就是 dp[i]。
                    if(isPalindrome(s, j + 1, i))
                    { 
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                    // 如果 s[j + 1, i] 不是回文串，尝试下一个分割边界。
                }
            }
            return dp[len - 1];
        }
    
        public static boolean isPalindrome(String s, int left, int right)
        { 
            while(left < right)
            { 
                if(s.charAt(left) != s.charAt(right))
                { 
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    
        public static void main(String[] args) { 
            String s = "aab";
            int res = minCut(s);
            System.out.println(res);
        }
    }

# 参考： #

1.  [动态规划（Java、Python）][Java_Python]
2.  [Manacher O(1)判断任意子串是否回文][Manacher O_1]
3.  [详细通俗的思路分析，多解法][Link 1]
4.  [自顶向下和自底向上][Link 2]
5.  [动态规划，四要素][Link 3]
6.  [动态规划，回溯 逐行解释 python3][_ python3]

[132. _ II]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f1f13865ca7543a7ab733d3cec8a4811.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/91a619e09a534447bec74a1eb019101c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/757847d5e1f64a55b170b029e2be930c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/2e2abcb44e2b4a7099835c6b32394bce.png
[Java_Python]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/
[Manacher O_1]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/manacher-o1pan-duan-ren-yi-zi-chuan-shi-fou-hui-we/
[Link 1]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-8/
[Link 2]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/zi-ding-xiang-xia-he-zi-di-xiang-shang-by-powcai-2/
[Link 3]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-si-yao-su-by-a380922457-10/
[_ python3]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-hui-su-zhu-xing-jie-shi-python3-b/