`

LeetCode - Palindrome Partitioning II

阅读更多

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.

首先设置dp变量 cuts[len+1]。cuts[i]表示从第i位置到第len位置(包含,即[i, len])的切割数(第len位置为空)。

初始时,是len-i。比如给的例子aab,cuts[0]=3,就是最坏情况每一个字符都得切割:a|a|b|' '。cuts[1] = 2, 即从i=1位置开始,a|b|' '。

cuts[2] = 1 b|' '。cuts[3]=0,即第len位置,为空字符,不需要切割。

上面的这个cuts数组是用来帮助算最小cuts的。

还需要一个dp二维数组matrixs[i][j]表示字符串[i,j]从第i个位置(包含)到第j个位置(包含) 是否是回文。

如何判断字符串[i,j]是不是回文?

1. matrixs[i+1][j-1]是回文且 s.charAt(i) == s.charAt(j)。

2. i==j(i,j是用一个字符)

3. j=i+1(i,j相邻)且s.charAt(i) == s.charAt(j)

当字符串[i,j]是回文后,说明从第i个位置到字符串第len位置的最小cut数可以被更新了,

那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。

即,Math.min(cuts[i], cuts[j+1]+1) 

最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉,即为最终结果。

public int minCut(String s) {
    if(s==null||s.length()<=1) return 0;
    int n = s.length();
    int[] cuts = new int[n+1];
    boolean[][] palin = new boolean[n][n];
    for(int i=0; i<n; i++) {
        cuts[i] = n-i;
    }
    for(int i=n-1; i>=0; i--) {
        for(int j=i; j<n; j++) {
            if(s.charAt(i)==s.charAt(j) && (j-i<2 || palin[i+1][j-1])) {
                palin[i][j] = true;
                cuts[i] = Math.min(cuts[i], cuts[j+1]+1);
            }
        }
    }
    return cuts[0]-1;
}

 

还有另外一种写法。

palin[i][j]表示字符串s的子串s[i...j]是否为回文串,cuts[j]表示子串s[0...j]所需要的最小分割数。

public int minCut(String s) {
    if(s==null||s.length()<=1) return 0;
    int n = s.length();
    int[] cuts = new int[n];
    boolean[][] palin = new boolean[n][n];
    for(int j=0; j<n; j++) {
        cuts[j] = j;
        for(int i=0; i<=j; i++) {
            //如果子串 s[i...j]是回文串
            if(s.charAt(i)==s.charAt(j) && (j-i<=1 || palin[i+1][j-1])) {
                palin[i][j] = true;
                //如果 s[0...j]是回文串,则说明不需要切割
                cuts[j] = Math.min(cuts[j], i>0 ? cuts[i-1]+1 : 0);
            }
        }
    }
    return cuts[n-1];
}

 

LeetCode上还有一个更好的解法,不需要使用二维数组来保存是否为回文:

https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

public int minCut(String str) {
    char[] s = str.toCharArray();
    int n = s.length;
    
    int[] cut = new int[n+1];  // number of cuts for the first k characters
    for (int i = 0; i <= n; i++) cut[i] = i-1; // initialize cuts to worst
    
    for (int i = 0; i < n; i++) {
        // odd length palindrome
        for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) {
            cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j]);
        }
        // even length palindrome
        for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) {
            cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j+1]);
        }
    }
    
    return cut[n];
}

 

上述代码还是不好理解,我每次都要花好长时间才能理解。又重构了下代码,下面这个是目前最好理解的写法:

public int minCut(String s) {
    int n = s.length();
    if(n <= 1) return 0;
    int[] f = new int[n+1];
    for(int i=0; i<=n; i++) f[i] = i-1; // worst case
    
    for(int i=0; i<n; i++) {
        // odd length palindrome
        for(int l=i, r=i; l>=0 && r<n && s.charAt(l) == s.charAt(r); l--, r++) {
            f[r+1] = Math.min(f[r+1], f[l] + 1);
        }
        // even length palindrome
        for(int l=i, r=i+1; l>=0 && r<n && s.charAt(l) == s.charAt(r); l--, r++) {
            f[r+1] = Math.min(f[r+1], f[l] + 1);
        }
    }
    return f[n];
}

  

Reference:

http://www.cnblogs.com/springfor/p/3891896.html

http://www.acmerblog.com/palindrome-partitioning-ii-6148.html

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning-ii.html

分享到:
评论

相关推荐

    python-leetcode题解之132-Palindrome-Partitioning-II

    在众多的LeetCode题库中,“Palindrome Partitioning II” 是一个有趣的字符串处理问题,属于动态规划和字符串分割的范畴。这个问题要求我们编写一个函数,接受一个字符串s作为输入,然后找到使字符串s的子串都是...

    js-leetcode题解之132-palindrome-partitioning-ii.js

    JavaScript解决方案专题——LeetCode题解之132题——分割回文串 II(palindrome-partitioning-ii.js) 在本篇文章中,我们将会探讨LeetCode中的132题——分割回文串 II。此题目要求我们对给定的字符串进行分割,...

    python-leetcode题解之131-Palindrome-Partitioning

    4. Palindrome Partitioning(回文划分):是本题的核心问题,即要求将给定的字符串划分为尽可能多的回文子串。回文是指正读和反读都相同的字符串。 5. 动态规划(Dynamic Programming):一种算法设计方法,它将...

    js-leetcode题解之131-palindrome-partitioning.js

    在JavaScript中,处理leetcode上的编程题目时,正确理解和解决"131.Palindrome Partitioning"这类字符串划分问题是一项重要的技能。本题要求编写一个函数,该函数将给定的字符串划分为尽可能多的回文子字符串,并...

    數位之和leetcode-leetcode-cpp:我的LeetCodeC++答案

    partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which exists once/twice... - count

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    gas station leetcode 在牛客网上的在线编程...palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 ...Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar

    leetcode力扣是什么-leetcode:leetcodebytags按自己整理的一些类别

    leetcode力扣是什么 leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是最好按照类别刷题,总结思路;...Partitioning (hard) 212 Word Search II (hard) DFS /二叉树 the difference between df

    leetcode338-LeetCode:力码

    分割回文串(Palindrome Partitioning)**:这是一个关于字符串处理的题目,要求将一个字符串分割成若干个回文子串。主要涉及的算法是深度优先搜索(DFS),通过递归的方式检查所有可能的分割方案,判断是否都是回文。 ...

    Leetcode部分解答(126题)

    1. **Palindrome Partitioning (mine).cpp** - 这个文件是关于LeetCode的第131题“回文分割”。该问题要求将一个字符串分割成多个回文子串。解冑通常涉及深度优先搜索或动态规划,寻找所有可能的分割方案并检查是否...

    leetcode添加元素使和等于-leetcode:leetcode

    Palindrome_Partitioning DP,避免递归调用,利用数组储存已算出来的数值,由后向前逐渐增加字符串处理 Palindrome_Partitioning_2 同上 Sum_Root_to_Leaf_Numbers DFS Surrounded_Regions 由四周‘O’开始向内检索...

    Selective_Leetcode_solutions

    3. 题目131 - "Palindrome Partitioning" 这是一道回文子串分割问题,要求将一个字符串分割成多个回文子串。常见的解法是动态规划,创建一个二维数组来存储子问题的最优解。在Java中,可以使用StringBuilder和...

    PythonAlgo:用Python解决Leetcode问题

    对于更高级的题目,可能会涉及图论或动态规划,比如`0131_palindrome_partitioning.py`可能涉及回文子串分割,这通常会用到动态规划来避免重复计算。 在PythonAlgo项目中,每个问题的解决方案都提供了清晰的思路和...

Global site tag (gtag.js) - Google Analytics