本篇推文共計(jì)2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

給你一個字符串s，請你將s分割成一些子串，使每個子串都是回文。

返回符合要求的最少分割次數(shù)。

示例：

輸入：s = "aab"
輸出：1
解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串。

輸入：s = "a"
輸出：0
解釋：不需要分割，s本身就是回文字符串

輸入：s = "ab"
輸出：1
解釋：在a和b之間切割一次，a和b分別構(gòu)成一個回文字符串

02

方法和思路

根據(jù)題意可知，

需要返回所有結(jié)果個數(shù)。

若字符串s為回文數(shù)，則返回0，

表示當(dāng)前字串不需要分割

我們可以初始化當(dāng)前字串最小分割次數(shù)res=Max

float("inf")
#正無窮

float("-inf")
#負(fù)無窮

定義遍歷結(jié)束索引i，遍歷區(qū)間[1,N+1)

N為字符串長度

若s[0,?,i?1]為回文串：

res=min(res,minCut(s[i,?,n?1])+1)。
解釋：始終保存最小的切割次數(shù)。

最后返回res

因?yàn)楸绢}可能會涉及到大量的比較，為了提供代碼運(yùn)行效率，較少運(yùn)行時間，我們引入裝飾器。

functools.lru_cache()

functools.lru_cache()是一個裝飾器，為函數(shù)提供緩存功能。在函數(shù)下次以相同參數(shù)調(diào)用時，可以直接返回上一次的結(jié)果。大大降低代碼運(yùn)行時間。

我們可以用生成第n個斐波納契數(shù)的過程，對比使用該裝飾器的時間消耗：

斐波那契數(shù)列指的是這樣一個數(shù)列：
數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 
144, 233，377，610，987，1597，2584，4181，
6765，10946，17711，28657，46368........

不用裝飾器時候的代碼：

import time
def fibonacci(n):
    """斐波那契函數(shù)"""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30))
#斐波那契函數(shù)的第30個數(shù)字
    print("total time is %.3fs" % (time.time() - stime))
#代碼計(jì)算時間消耗

此時輸出為：

832040
total time is 0.374s

用裝飾器時候的代碼：

import time
import functools
@functools.lru_cache(None)

def fibonacci(n):
    """斐波那契函數(shù)"""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30))
#斐波那契函數(shù)的第30個數(shù)字
    print("total time is %.3fs" % (time.time() - stime))
#代碼計(jì)算時間消耗

此時輸出為：

832040
total time is 0.000s

我們用代碼解答本題為：

import functools
class Solution:
    @functools.lru_cache(None)
    def minCut(self, s: str) -> int:
        if s==s[::-1]:
            return 0
        res=float("inf")
        for i in range(1,len(s)+1):
            if s[:i]==s[:i][::-1]:
                res=min(self.minCut(s[i:])+1,res)
        return res