Akik Look at that coder

Public account: Look at that code farmer

132. Split palindrome string II

Title description:

Given a string s, please split s into substrings so that each substring is palindrome.

Returns the minimum number of splits that meet the requirement.

Example: Enter s ="aab"Output:1Explanation: only one partition is required to divide S into ["aa"."b"] two such a subroutine string. Enter: s ="a"Output:0Explanation: No need to split, s itself is palindrome string input: s ="ab"Output:1Explanation: Cut once between a and B to form a palindrome string, respectivelyCopy the code

The code analysis

A. the b. the C. the D. the

We need to return all the results.

If the string s is a palindrome, 0 is returned,

Indicates that the current string does not need to be split

We can initialize the current minimum number of string splits res=Max

float("inf") # infinity float("-inf") # minus infinityCopy the code

Define traversal end index I, traversal interval [1,N+1]

N is the length of a string

If S [0…, I −1] is a palindrome string:

Res = min (res, minCut (s/I,..., n -1]) +1). Explanation: Always save the minimum number of cuts. Finally return resCopy the code
Because this problem is likely to involve a lot of comparisons, we introduced decorators to provide efficiency and less runtime. functools.lru_cache()Copy the code

Functools.lru_cache () is a decorator that provides caching for functions. The next time the function is called with the same argument, the result of the previous call can be returned directly. Greatly reduces code runtime.

We can compare the time spent using the decorator with the process of generating the NTH Fibonacci number:

The Fibonacci sequence refers to a sequence in which the sequence begins at no3You start with terms that are equal to the sum of the previous two terms.1.1.2.3.5.8.13.21.34.55.89.144.233.377.610.987.1597.2584.4181.6765.10946.17711.28657.46368..Copy the code

Code without decorators:

import time
def fibonacci(n):
    ""Fibonacci function""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30) # order of Fibonacci function30A digital print ("total time is %.3fs"% (time.time() -stime)) #Copy the code

The output is:

832040
total time is 0.374s
Copy the code

Code for using decorators:

import time
import functools
@functools.lru_cache(None)

def fibonacci(n):
    ""Fibonacci function""
    if n < 2:
        return n
    return fibonacci(n - 2) + fibonacci(n - 1)

if __name__ == '__main__':
    stime = time.time()
    print(fibonacci(30) # order of Fibonacci function30A digital print ("total time is %.3fs"% (time.time() -stime)) #Copy the code

The output is:

832040
total time is 0.000s
Copy the code

We use the code to answer the question as:

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
Copy the code

If you find this helpful:

1. Click “like” to support it, so that more people can see this article

2, pay attention to the public number: look at that code farmers, we study together and progress together.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign