leetcode刷题笔记一百三十一与一百三十二题 分割回文串与分割回文串II
源地址：
131问题描述：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
/**
131题主要基于回溯法解决问题
尝试对各个位置的字符进行分割，当前缀字符串为回文串时，对后缀字符串进行分割，如果可顺利分割即start到达末尾，则将分割结果Path加入res中
*/
import scala.collection.mutable
object Solution {
def partition(s: String): List[List[String]] = {
val length = s.length
val res = mutable.ListBuffer[List[String]]()
if (length == 0) return List()
var path = mutable.ListBuffer[String]()
dfs(s, 0, length)
//return res.toList
def dfs(str: String, start: Int, length: Int): Unit = {
if (start == length){
res += path.toList
return
}
for (i <- start to length-1){
if (check(str, start, i)){
path += str.substring(start, i+1)
dfs(s, i+1, length)
path = path.dropRight(1)
}
}
}
def check(str: String, left: Int, right: Int): Boolean = {
var leftPos = left
var rightPos = right
while (leftPos < rightPos){
if (str.charAt(leftPos) != str.charAt(rightPos)) return false
leftPos += 1
rightPos -= 1
}
return true
}
return res.toList
}
}
132问题描述：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
/**
本题使用动态规划思想方法
初始状态：(由于单个字符可认为是回文串，故如果字符串的单个字符一个个分开可认为分割成功) 0 <= i <= length-1 dp(i) = i
设当前字符串直接就是回文串，则dp(i) = 0 ,即不用分割
否则需要进行分割，依次对字符位置进行分割，若分割后缀字符串也为回文串，更新
状态转换方程：
0 <= j <= i-1 dp(i) = Math.min(dp(i), dp(j)+1)
*/
object Solution {
def minCut(s: String): Int = {
val length = s.length
if (length < 2) return 0
val dp = Array.fill(length)(0)
for (i <- 0 to length-1) dp(i) = i
for (i <- 1 to length-1){
if (check(s, 0, i)) dp(i) = 0
else{
for (j <- 0 to i-1){
if (check(s, j+1, i)) dp(i) = Math.min(dp(i), dp(j)+1)
}
}
}
def check(str: String, left: Int, right: Int): Boolean = {
var leftPos = left
var rightPos = right
while (leftPos < rightPos){
if (str.charAt(leftPos) != str.charAt(rightPos)) return false
leftPos += 1
rightPos -= 1
}
return true
}
return dp(length-1)
}
}