/// 2.单词拆分
/// - Parameters:
/// - s: <#s description#>
/// - wordDict: <#wordDict description#>
/// - Returns: <#description#>
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
if(s.count == 0){
// 过滤空字符串
return true
}
// 用 26 个字母首字母为桶，装桶
var buckets:[String:[String]] = [:]
for word in wordDict {
if word.count > 0 {
let first = word.prefix(1)
if var _ = buckets[String(first)] {
buckets[String(first)]!.append(word)
}else {
buckets.updateValue([word], forKey: String(first))
}
}
}
// 初始化dp数组
var dp:[Bool] = Array.init(repeating: false, count: s.count)
// 截取第一个字符
let first = saAndsa(s: s, index: 0)
// 第一个字符没匹配上，直接false
guard let bucket = buckets[first] else { return false }
// 根据第一个字符的桶，赋值第一批 dp = true
for word in bucket {
let length = word.count
let subStr = String(s.prefix(length))
if word == subStr {
dp[length-1] = true
}
}
/*
动态规划函数：
如果当前字符串满足条件，那么必定存在中间一个节点 j , 0 - j 被完整截取， j - s.count 是一个单词
*/
// 第一重遍历，外层遍历，所有可能
for i in 0...s.count-1 {
// 当前遍历到 i， iStr = 当前截取到的完整字符串
let iStr = String(s.prefix(i+1))
// 内层遍历，找到那个节点 j
for j in 0...i {
// 从后往前截取，其实直接截取最后一个单词就可以了？
let i_j = String(iStr.suffix(i-j))
// 从后面截取的是否符合单词
let jFirst = String(i_j.prefix(1))
if let bucket = buckets[jFirst] {
// 这里用 && 真的大大节省了效率，dp[j] == false，那么这个j就不会是节点
if(dp[j] == true && contain(s: i_j, bucket: bucket)){
// 如果这段字符串包含满足条件的 j 节点，那么他就是符合条件的
dp[i] = true
}
}
}
}
return dp[s.count-1]
}
func contain(s:String,bucket:[String])->Bool{
for word in bucket {
if (s == word){
return true
}
}
return false
}
func saAndsa(s:String,index:Int)->String{
let startIndex = s.index(s.startIndex, offsetBy: index)
let endIndex = s.index(startIndex, offsetBy: 1)
let res = String(s[startIndex..<endIndex])
return res
}
/// 3.最长回文子序列
/// - Parameter s: <#s description#>
/// - Returns: <#description#>
func longestPalindromeSubseq(_ s: String) -> Int {
var dp:[Combination:Int] = [:]
let count = s.count
if count == 0 || count == 1 {
return count
}else if(count == 2){
if saAndsa(s: s, index: 0) == saAndsa(s: s, index: 1){
return 2
}else {
return 1
}
}
// 范围长度 i
for i in 1...count {
// 遍历的次数
for j in 1...count-i+1 {
let keyi = j-1
let keyj = (j-1)+i-1
let key = Combination(i: keyi,j: keyj)
if (i == 1){
// 长度为1，绝对是回文
dp.updateValue(1, forKey: key)
}else if(i == 2) {
// 长度为2，比较左右
if(saAndsa(s: s, index: keyi) == saAndsa(s: s, index: keyj)){
dp.updateValue(2, forKey: key)
}else {
dp.updateValue(1, forKey: key)
}
}else if(i == 3){
// 长度为3，比较中间的
if (saAndsa(s: s, index: keyi) == saAndsa(s: s, index: keyj)){
dp.updateValue(3, forKey: key)
}else {
// 比较左右两个dp
let combinationLeft = Combination(i: keyi,j: keyi + 1)
let combinationRight = Combination(i: keyj - 1,j: keyj)
dp.updateValue(max(dp[combinationLeft]!, dp[combinationRight]!), forKey: key)
}
}else {
// 其他长度，如果左右相同，那么中间的加2，如果左右不相同，取左或右的最大值，左右最大值，当中间的两个端不同，那么比较，如果中间两个端相同，不变
let combinationMid = Combination(i: keyi + 1,j: keyj - 1)
let combinationLeft = Combination(i:keyi,j: keyj - 1)
let combinationRight = Combination(i:keyi+1,j: keyj)
if(saAndsa(s: s, index: keyi) == saAndsa(s: s, index: keyj)){
dp.updateValue(dp[combinationMid]! + 2, forKey: key)
}else {
dp.updateValue(max(dp[combinationLeft]!, dp[combinationRight]!), forKey: key)
}
}
}
}
return dp[Combination(i: 0,j: count-1)]!
}
/// 4.编辑问题
/// - Parameters:
/// - word1: <#word1 description#>
/// - word2: <#word2 description#>
/// - Returns: <#description#>
func minDistance(_ word1: String, _ word2: String) -> Int {
// 优化空间复杂度
var dpi_1:[Combination:Int]=[:]
var dpi:[Combination:Int]=[:]
// 根据公式建立二维数组
for i in 0...word1.count {
dpi.removeAll()
// 0代表空串，i = word1 字符长度
for j in 0...word2.count {
// 0代表空串，j = word1 字符长度
if i == 0 {
dpi[Combination(i: 0,j: j)] = j
}else if(j == 0){
dpi[Combination(i: i,j: 0)] = i
}else {
var lastWordSame = 1
if(saAndsa(s: word1, index: i-1) == saAndsa(s: word2, index: j-1)){
lastWordSame = 0
}
/*
解题核心：建立dp函数
1.dp[i,j]：i对应的word1长度，j对应的word2长度
2.dp[i,j]的最短编辑数 = min（dp[i-1,j]+1,dp[i,j-1]+1,dp[i-1,j-1]+word1[last] == word2[last]）
3.优化空间复杂度(非常重要),dp只需要记录两行，i与i-1
*/
dpi[Combination(i: i,j: j)] = min(dpi_1[Combination(i: i-1,j: j)]! + 1, dpi[Combination(i: i,j: j-1)]! + 1,dpi_1[Combination(i: i-1,j: j-1)]! + lastWordSame)
}
}
dpi_1 = dpi
}
return dpi[Combination(i: word1.count,j: word2.count)]!
}
/// 5.两个字符串的最小ASCII删除和
/// - Parameters:
/// - s1: <#s1 description#>
/// - s2: <#s2 description#>
/// - Returns: <#description#>
func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
var dp:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: s2.count + 1), count: s1.count + 1)
let s1Arr = s1.map{Int($0.asciiValue!)}
let s2Arr = s2.map{Int($0.asciiValue!)}
for m in 1...s1Arr.count {
// m 代表长度，所以值是累加和
dp[m][0] = s1Arr.prefix(m).reduce(0, +)
}
for n in 1...s2Arr.count {
dp[0][n] = s2Arr.prefix(n).reduce(0, +)
}
for m in 1...s1Arr.count {
for n in 1...s2Arr.count {
let valueM = s1Arr[m-1]
let valueN = s2Arr[n-1]
if valueM == valueN {
dp[m][n] = dp[m-1][n-1]
}else {
// 当 s1[m] 与 s2[n-3] 相同 ，这种情况已经包含在 dp[m+1][n-2] 中
dp[m][n] = min(dp[m-1][n] + valueM, dp[m][n-1] + valueN)
}
}
}
return dp[s1Arr.count][s2Arr.count]
}
网友评论