Lever's Castle

583. 两个字符串的删除操作

December 21, 2018

https://leetcode-cn.com/problems/delete-operation-for-two-strings/

使用语言: Golang

解题思路

最少删除数 = 两个字符串的字符总数 - 2 * 最大公共子字符数有多少个字母相同，长度 * 2，用两个字符串的总长减去这个值，就是所求值

方案一

func countSame (word1 string, i int, word2 string, j int, count int) int {
    if i >= len(word1) || j >= len(word2) {
        return count
    }

    if word1[i] == word2[j] {
        return countSame(word1, i + 1, word2, j + 1, count + 1)
    }
    
    count1 := countSame(word1, i, word2, j + 1, count)
    count2 := countSame(word1, i + 1, word2, j, count)
    
    if (count1 < count2) {
        return count2
    }
    return count1
}

func minDistance(word1 string, word2 string) int {
    return len(word1) + len(word2) - countSame(word1, 0, word2, 0, 0) * 2
}

这个解法用递归的思想很容易想到：

最小子问题：字符相等且顺序一致的字符个数，并求出其中的最大值
边界：i 超过 word1 长度或者 j 超过 word2 长度时，如何处理？

可惜这个方案在求解用例 “dinitrophenylhydrazine” 和 “acetylphenylhydrazine” 的删除数时，超时狗带了，我在本地也跑了十分钟左右才算出答案来。

时间复杂度应该是 O(2^(max(len(word1), len(word2))))，可以这么理解 —— 每次递归执行两次计算 countSame 的操作，而递归的深度是由最长的字符串决定的。

也就是说这个方案太过简单粗暴了，需要优化下。

方案二

func countSame (word1 string, i int, word2 string, j int, memo [][]int) int {
    if i >= len(word1) || j >= len(word2) {
        return 0
    }
    
    if memo[i][j] > 0 {
        return memo[i][j]
    }

    if word1[i] == word2[j] {
        memo[i][j] = 1 + countSame(word1, i + 1, word2, j + 1, memo)
        return memo[i][j]
    }
    
    count1 := countSame(word1, i, word2, j + 1, memo)
    count2 := countSame(word1, i + 1, word2, j, memo)
    
    if count1 < count2 {
        memo[i][j] = count2
    } else {
        memo[i][j] = count1
    }
    
    return memo[i][j]
}

func minDistance(word1 string, word2 string) int {
    memo := make([][]int, len(word1))
    for i := 0; i < len(word1); i++ {
        memo[i] = make([]int, len(word2))
    }
    return len(word1) + len(word2) - countSame(word1, 0, word2, 0, memo) * 2

}

仍然使用递归的方式计算，不同的是，新构造了一个二维数组 memo，用来存上次计算的结果，这样可以在重复递归同一条路径时，节省一些时间复杂度。

这种方式是以空间换时间，我们用一个 m * n 的空间把时间复杂度降到了 O(m * n)

痕迹
没有过去，就没法认定现在的自己