mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 08:02:30 +08:00
43 lines
651 B
Go
43 lines
651 B
Go
package leetcode
|
|
|
|
func minCut(s string) int {
|
|
if s == "" {
|
|
return 0
|
|
}
|
|
result := len(s)
|
|
current := make([]string, 0, len(s))
|
|
dfs132(s, 0, current, &result)
|
|
return result
|
|
}
|
|
|
|
func dfs132(s string, idx int, cur []string, result *int) {
|
|
start, end := idx, len(s)
|
|
if start == end {
|
|
*result = min(*result, len(cur)-1)
|
|
return
|
|
}
|
|
for i := start; i < end; i++ {
|
|
if isPal(s, start, i) {
|
|
dfs132(s, i+1, append(cur, s[start:i+1]), result)
|
|
}
|
|
}
|
|
}
|
|
|
|
func min(a int, b int) int {
|
|
if a > b {
|
|
return b
|
|
}
|
|
return a
|
|
}
|
|
|
|
func isPal(str string, s, e int) bool {
|
|
for s < e {
|
|
if str[s] != str[e] {
|
|
return false
|
|
}
|
|
s++
|
|
e--
|
|
}
|
|
return true
|
|
}
|