37 lines
949 B
Swift
37 lines
949 B
Swift
func solve() -> Int {
|
|
guard let input = readLine() else { return -1 }
|
|
let str = Array(input)
|
|
let N = str.count
|
|
|
|
var isPalindrom: [[Bool]] = Array(repeating: Array(repeating: false, count: N), count: N)
|
|
|
|
for len in 1...N {
|
|
for start in 0...N-len {
|
|
let end = start + len - 1
|
|
|
|
if (len == 1) || (len == 2 && str[start] == str[end]) || (str[start] == str[end] && isPalindrom[start+1][end-1]) {
|
|
isPalindrom[start][end] = true
|
|
}
|
|
}
|
|
}
|
|
|
|
var dp: [Int] = Array(repeating: 2501, count: N)
|
|
|
|
for end in 0..<N {
|
|
for start in 0...end {
|
|
if isPalindrom[start][end] {
|
|
if start == 0 {
|
|
dp[end] = 1
|
|
}
|
|
else {
|
|
dp[end] = min(dp[start - 1] + 1, dp[end])
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return dp[N-1]
|
|
}
|
|
|
|
print(solve())
|