leetcode每日一题之10.分割回文串 II

分割回文串 II

解题思路

跟最长递增子序列思路一样，使用动态规划。

定义 dp[i] 为结尾为i的最小回文串次数.

1. 当[0,i]为回文串时，则dp[i]为0

2. 当[0,i]不为回文串时，

   循环求最小的分割次数

如何循环

从0开始一直到i-1，作为j。如果[j + 1, i]为回文串，则取dp[j] + 1.

代码

class Solution {

    public $palindromeArray;
    /**
     * @param String $s
     * @return Integer
     */
    function minCut($s) {
        $length = strlen($s);
        if($length < 2) return 0;
        // 动态规划求所有的子串是否为回文串
        $this->setpalindromeArray($s, $length);
        $dp = [];
        for($i =0; $i < $length; ++ $i){
            $dp[$i] = $i;
        }
        for($i = 1; $i < $length; ++$i){
            if($this->palindromeArray[0][$i]){
                $dp[$i] = 0;
            } else {
                for($j = 0; $j < $i; ++$j){
                    if($this->palindromeArray[$j + 1][$i]){
                        $dp[$i] = min($dp[$i], $dp[$j] + 1);
                    }
                }
            }
        }
        return $dp[$length - 1];
    }

    function setpalindromeArray($string, $length){
        for($right = 0; $right < $length; ++$right){
            for($left = $right; $left >=0; --$left){
                if($string[$left] == $string[$right] && ($right - $left < 2 || $this->palindromeArray[$left + 1][$right - 1])){
                    $this->palindromeArray[$left][$right] = true;
                } else {
                    $this->palindromeArray[$left][$right] = false;
                }
            }
        }
    }
}