Problem

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

Example
Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

思路:

• 假设一个长度为n的字符串, i 为某一位,
• 首先看问题是否能由子问题组成
• (0 到 n) 字符串 的min cuts 能够分解 成为 (0 到 i) 的min cuts + 1, 只要在substring(i, n) 是回文串的前提下

• 时间复杂度:

  • O(n ^ 3)

•   public int minCut(String s) {
        if (s == null) {
            return 0;
        }
  
        int n = s.length();
        int[] f = new int[n + 1];
  
        for (int i = 0; i < n + 1; i++) {
            f[i] = i;
        }
  
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                String sub = s.substring(j, i);
                if (isPalindrome(sub)) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[n] - 1;
    }
  
    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
  
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
  

  ---

优化

• 循环中每次调用isPalindrome函数需要花费O(n)时间.
• 从这里入手, 空间换时间, 转换成O(1)
• 定义一个二维数组, p[start][end], 一维代表字符串的头位置, 第二维代表末尾, 值代表是否为回文串

    public int minCut(String s) {
        if (s == null) {
            return 0;
        }

        int n = s.length();
        int[] f = new int[n + 1];

        boolean[][] isPalindrome = getIsPalindrome(s);

        for (int i = 0; i < n + 1; i++) {
            f[i] = i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                String sub = s.substring(j, i);
                if (isPalindrome[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[n] - 1;
    }

    private boolean[][] getIsPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        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 || dp[i + 1][j - 1])) {
              dp[i][j] = true;
            }
          }
        }

        return dp;
    }

判断一个字符串内所有的子串是否为回文串, 设计循环不变式

• dp[i][j] = true
  • i <= j < n
    • when j - i > 2, s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]
    • when j - i <= 2, s.charAt(i) == s.charAt(j)