目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

二、解题思路

假设每个字符间都需要分割得到单一字符形式的回文，那么分割的次数逐次递增；

假设i从1到s的长度，而j在[0, i)之间，实际上就是找区间[j,i)间的字符串是否为回文；

如果是，那么i位置记录的切割次数就是原始i位置记录的切割次数与j位置记录的切割次数加1；

例如aab，memory里的变化如下：

[-1, 0, 1, 2]

[-1, 0, 0, 2]

[-1, 0, 0, 1]

因为aa之间不需要切割了，所以第二a的位置记录的切割次数本来是1，但是就变为0了，aa是回文；

所以到b这个位置，最小切割次数不是2而是1(第二个a的0加1)；

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def minCut(self, s: str) -> int:
     
    
   

    

     

    
    

     
 if not s:
     
    
   

    

     

    
    

     
 return 0
     
    
   

    

     

    
    

     

       memory = [i for i in range(-1, len(s))]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for i in range(1, len(s) + 1):  # i从1开始
     
    
   

    

     

    
    

     
 for j in range(i):  # 区间[j, i)
     
    
   

    

     

    
    

     
 if s[j:i] == s[j:i][::-1]:
     
    
   

    

     

    
    

     

       memory[i] = min(memory[i], memory[j] + 1)
     
    
   

    

     

    
    

     
 return memory[-1]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == "__main__":
     
    
   

    

     

    
    

     

       ss = Solution()
     
    
   

    

     

    
    

     

       s = "aaa"
     
    
   

    

     

    
    

     

       ans = ss.minCut(s)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/114522523