72. 编辑距离

动态规划。先要找状态方程

截屏2022-07-06 11.16.11.png

1、删除操作的时候
同一列的字符串 上边的是由下边的长的字符 最少删除一个字符得到的
d[i][j] = d[i - 1][j] + 1
2、插入操作的时候
d[i][j] = d[i][j - 1] + 1
3、替换操作的时候
如果最后一个字符不相同
s1[i - 1] != s2[j - 1]
最少的操作 = 需要上一个位置的字符串转换完成之后 + 替换操作
d[i][j] = d[i - 1][j - 1] + 1
如果最后一个位置的字符相同
s1[i - 1] == s2[j - 1]
最少的操作 = 需要上一个位置的字符串转换完成之后
d[i][j] = d[i - 1][j - 1]

func minDistance(_ word1: String, _ word2: String) -> Int {

        let wordArray1 = Array(word1)
        let wordArray2 = Array(word2)
        let row = wordArray1.count , col = wordArray2.count
        //初始化数组
        let temp = Array.init(repeating: 0, count: col + 1)
        var valueArray = Array.init(repeating: temp, count: row + 1)
        
        for i in 0...row {
            
            for j in 0...col {
                
                if i == 0 && j == 0 {
                    valueArray[i][j] = 0
                }else if i == 0 {
                    valueArray[0][j] = j
                }else if j == 0 {
                    valueArray[i][0] = i
                }else {
                    //尝试删除操作
                    valueArray[i][j] = valueArray[i - 1][j] + 1
                    //尝试插入操作
                    valueArray[i][j] = min(valueArray[i][j],valueArray[i][j - 1] + 1)
                    //尝试替换操作
                    //最后一个字符不相同
                    if wordArray1[i - 1] != wordArray2[j - 1] {
                        
                        valueArray[i][j] = min(valueArray[i][j],  valueArray[i - 1][j - 1] + 1)
                        
                    }else{
                        valueArray[i][j] = min(valueArray[i][j],valueArray[i - 1][j - 1])
                    }

                    
                }
                
            }
        }
                
        
          return valueArray[row][col]
    
    }