四、字符串相关

/// 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]
}