132. Palindrome Partitioning II

2017-04-29 本文已影响45人 DrunkPian0

DFS不能AC

这题我想像 131题那样dfs把所有解找到然后找到需要cut最短的那一个，用一个全局变量保存minCut，每次解出来之后判断是否需要更新。我自己测试了没问题，但提交的时候TLE了。

    int minCut;

    public int minCut(String s) {
        if (s == null || s.equals("")) return 0;
        minCut = s.length() - 1;
        backtrack(new ArrayList<String>(), s, 0);
        return minCut;
    }

    public void backtrack(List<String> tempList, String s, int start) {
        if (start == s.length()) {
            if (tempList.size() - 1 < minCut) minCut = tempList.size() - 1;
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                tempList.add(s.substring(start, i + 1));
                backtrack(tempList, s, i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low <= high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }

我也有考虑能不能用带返回值的dfs来写，但是想不到，因为跟boolean不同，int需要代入到下一次递归。

这题不能用131的dfs，摘抄一段code ganker的解释：

做过Word Break的朋友可能马上就会想到，其实两个问题非常类似，当我们要返回所有结果（Palindrome Partitioning和Word Break II）的时候，使用动态规划会耗费大量的空间来存储中间结果，所以没有明显的优势。而当题目要求是返回某个简单量（比如Word Break是返回能否切割，而这道题是返回最小切割数）时，那么动态规划比起brute force就会有明显的优势。

动态规划

这题的动态规划有点难，它需要一个二维数组和一个一维数组。
一维数组minCut[i]保存着s从头开始到i切分成palindrome需要的minCut；
二维数组pal[j][i]保存着从j到i的substring是不是palindrome。（i<n ; j<=i，也就是说用j把0到i的长度再拆分，判断j到i是不是pal，如果是，那j到i显然就不需要切了）

看着挺难了，理解了也就那么回事。但是这种题目让我自己想真是完全想不到。难点不仅在于两个状态的定义，转移方程也很难想到。另外，对于palindrome的判断，
s.charAt(i) == s.charAt(j) && pal[j+1][i-1])
这句要写在
(s.charAt(i) == s.charAt(j) && i - j <= 1
之后，否则i = 0会出现outofbounds。

还有i - j <= 1写成i - j <= 2也能AC，因为两个相同的数中间夹一个数也是palindrome。


    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        boolean[][] pal = new boolean[s.length()][s.length()];
        int[] minCut = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            minCut[i] = i;
            for (int j = 0; j <= i; j++) {
                if ((s.charAt(i) == s.charAt(j) && i - j <= 1 ||
                        s.charAt(i) == s.charAt(j) && pal[j+1][i-1])) {
                    pal[j][i] = true;
                    //因为j-1可能会outofbound，所以把j=0单独拎出来。也可以把转移方程倒过来写了，就是从后往前切。
                    if (j > 0) {
                        minCut[i] = Math.min(minCut[i], minCut[j - 1] + 1);
                    } else {
                        //j == i的时候切0刀
                        minCut[i] = 0;
                    }
                }
            }
        }
        return minCut[s.length() - 1];
    }

ref：

132. Palindrome Partitioning II

DFS不能AC

动态规划

猜你喜欢

热点阅读