力扣LeetCode 132. 分割回文串 II 困难->回溯代码片段

CodeSnippet.Cn
代码片段

力扣LeetCode 132. 分割回文串 II 困难->回溯

Algorithm

Python 小笨蛋发布于：2021年02月22日更新于：2021年02月22日 135

[132. 分割回文串 II](https://leetcode-cn.com/problems/palindrome-partitioning-ii/ "132. 分割回文串 II")

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。

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

**示例 2：**
```csharp
输入：s = "a"
输出：0
```

**示例 3：**
```csharp
输入：s = "ab"
输出：1
```

> 用回溯算法会超时！
> 其实就是求树的最小高度

```python
class Solution(object):
    def minCut(self, s):
        if not s: return 0
        cut = float('inf')

def backtrack(lastStr, step):
            if len(lastStr) == 0:
                nonlocal cut
                cut = min(cut, step)
                return

for i in range(len(lastStr)):
                first = lastStr[:i + 1]  # a
                last = lastStr[i + 1:]  # ab
                if not self.isPalindrome(first): continue

step += 1
                backtrack(last, step)
                step -= 1

backtrack(s, 0)
        return cut - 1

def isPalindrome(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

if __name__ == '__main__':
    solution = Solution()
    print(solution.minCut('aab'))
```

这里⇓感觉得写点什么，要不显得有点空，但还没想好写什么... 返回顶部