两个字符串上的删除操作

Question

LeetCode第583题

给你两个单词word1和word2，请问至少需要几次删除操作使得word1和word2变得一样？每一步你都可以从word1或者word2里删除一个字符。例如如果输入两个单词”sea”和”eat”，我们至少需要两步删除操作，分别删除第一个单词的’s’和第二个单词的’t’，使得它们变成相同的”ea”。

Analysis

此处是设计到动态规划问题最长公共子串（LCS, Longest Common Subsequence），这个问题实际上最长公共字串的应用。这是因为我们的目标是删除一些字符之后word1和word2相同，也就是剩下的是两个字符串的公共子串。剩下的公共子串越长，那么需要的删除操作就越少。

空间复杂度为O(mn)的解法

由于这是一个求解最优解的问题（“最长”公共子串），我们可以尝试应用动态规划。应用动态规划的第一步找出状态转移函数。我们用函数f(i,j)表示第一个字符串s1的前i个字符组成的子字符串和第二个字符串s2的前j个字符组成的子字符串的最长公共子串的长度。

我们分两种情况讨论这个函数。如果s1中的第i个字符和s2中的第j个字符相同，f(i,j)等于f(i-1,j-1)+1。这相当于在s1的前i-1个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的基础上增加了一个公共的字符。

如果s1中的第i个字符和s2中的第j个字符不同，f(i,j)等于f(i-1,j)和f(i,j-1)的较大值。既然s1中的第i个字符和s2中的第j个字符不同，我们可以忽略s1中的第i个字符，去看看在s1的前i-1个字符组成的子字符串和s2的前j个字符组成的子字符串的最长公共子串的长度，这就是f(i-1,j)的值。同样，我们也可以忽略s2中的第j个字符，去看看在s1的前i个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的长度，这就是f(i,j-1)的值。

由于状态转移函数有两个变量i和j，我们可以用一个二维矩阵来存储f(i,j)的值。
空间复杂度为O(n)的解法

针对上述空间复杂度为O(mn)的解法，发现在求解dp[i][j]的时候只用到了dp[i-1][j-i]、dp[i-1][j]和dp[i][j-1]，这三个值要么位于二维矩阵dp的第i-1行，要么位于dp的第i行。因此求任意一个dp[i][j]的时候，我们只要矩阵中的第i-1行和第i行这两行就够了，并不是真正需要保留所有的m+1行（假设m为第一个字符串s1的长度）。这样空间复杂度就降低到O(n)了。

接下来我们看能不能进一步减少空间的使用，只保留二维矩阵dp中的一行，也就是只保留一个一维数组。如果只保留二维矩阵中的一行，第i-1行第j-1的数值（即f(i-1,j-1)）和第i行j-1列的数值（即f(i,j-1)）都对应到一维数组中的第j-1个数值。可是我们在求f(i,j)又同时需要第i-1行第j-1列的数值和第i行j-1列的数值，因此我们需要确保它们两个在使用之前不能相互覆盖。

注意到f(i-1,j-1)的值只是在求解f(i,j)有用，之后再也不需要。因此我们在求解f(i,j)的时候，先不把f(i,j-1)的值写入到一维数组，而是用一个临时变量保存。在求解f(i,j)之后，再把f(i,j-1)写入到一维数组。此时即使把f(i-1,j-1)的值覆盖，也不会有任何问题。

Code

空间复杂度为O(1), 时间复杂度为min(O(nm^2/2),O(mn^2/2))

def longestCommonSubsequence(str1, str2):
    """最长公共子串"""
    for index in range(len(str1)):
        for indece in range(len(str2)):
            if str1[index] !=str2[indece]:
                continue
            else:
                max_length = min(len(str1)-index, len(str2)-indece)
                for length_index in range(max_length):
                    if str1[index : index + (max_length - length_index)]==\
                    str2[indece : indece + (max_length - length_index)]:
                        return str1[index : index + (max_length - length_index)]
    return None

def min_distance(str1, str2):
    lcs_str = longestCommonSubsequence(str1, str2)
    if lcs_str is None:
        return -1
    else:
        return len(str1) + len(str2) - 2*len(lcs_str)
    

print(min_distance("sea", "eat"))

空间复杂度为O(mn), 时间复杂度为O(mn)

import numpy as np
def longestCommonSubsequence_dp(str1, str2):
    """动态规划方法求最长公共子串的长度,时间空间复杂度均为O(mn)"""
    dp = np.zeros((len(str1)+1,len(str2)+1), dtype = np.int)
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[len(str1)][len(str2)]


def min_distance(str1, str2):
    lcs_len = longestCommonSubsequence_dp(str1, str2)
    return len(str1) + len(str2) - 2*lcs_len
    

print(min_distance("sea", "eat"))

空间复杂度为O(n)

import numpy as np
def longestCommonSubsequence_dp1(str1, str2):
    """动态规划方法求最长公共子串的长度,时间空间复杂度均为O(n)"""
    dp = np.zeros(len(str2)+1, dtype = np.int)
    for i in range(1,len(str1)+1):
        prev = 0
        for j in range(1,len(str2)+1):
            cur = dp[j-1]+1 if str1[i-1] == str2[j-1] else max(dp[j], prev)
            dp[j-1] = prev
            prev = cur
        dp[j] = prev
    return dp[len(str2)]


def min_distance(str1, str2):
    lcs_len = longestCommonSubsequence_dp1(str1, str2)
    return len(str1) + len(str2) - 2*lcs_len
    

print(min_distance("sea", "eat"))

1
2