在空间O(n)中寻找最长的公共子串

Question

我正在处理类问题，从两个字符串中查找最长的公共子字符串，但我希望返回最长的公共子字符串，而不是只返回最长的公共substring.like的大小。

s1 = 'abcdex', s2 = 'xbcdey' => 'bcde'
s1 = 'abcxyx', s2 = 'xbcydey' => 'bc'

我的方法是使用动态编程来创建一个备注表，并更新每个需要空间O(n * m)的单元格。我如何实现代码，使我只能使用空间作为O(n)？

    def longestCommonSubstring(self, s1, s2):
        """
        :type s: str
        :rtype: str
        """
        m, n = len(s1), len(s2)
        dp = [[''] * (n + 1) for _ in range(m + 1)]
        max_len = ''
        for i, ic in enumerate(s1):
            for j, jc in enumerate(s2):
                dp[i][j] = dp[i - 1][j - 1] + ic if ic == jc else ''
                max_len = dp[i][j] if len(max_len) < len(dp[i][j]) else max_len
        return max_len

Answer 1

PEP 8

您正在遵循大多数PEP 8风格的指导方针。其中一个方法名称应该是snake_case；您的函数应该命名为longest_common_substring。

棘手代码

您的dp矩阵由n+1正确地分配给大小m+1。

索引矩阵时，可以使用[i-1][j-1]和0 \le i \lt m访问0 \le j \lt n。这意味着您永远不会访问最后分配的行m或最后分配的列n，而是依赖于访问-1行和-1列来访问这些“未使用”的空格。这最多是“令人惊讶”的代码，如果翻译成不同的编程语言，则是“崩溃”代码。

最好在索引dp矩阵的索引中添加一个。最简单的方法是在一个地方启动i和j枚举：

    for i, ic in enumerate(s1, 1):
        for j, jc in enumerate(s2, 1):

无用else

展开以下... if ... else ...语句：

            max_len = dp[i][j] if len(max_len) < len(dp[i][j]) else max_len

最初，这会产生：

            if len(max_len) < len(dp[i][j]):
                max_len = dp[i][j]
            else:
                max_len = max_len

但是，我们可以立即看到else:子句是无操作的，并且可以删除：

            if len(max_len) < len(dp[i][j]):
                max_len = dp[i][j]

读起来比原来要清楚得多。

从O(n m)到O(n)空间

在外部循环的第一次迭代中，您只访问行-1和0。在外部循环的第二次迭代中，您只访问行0和1。在外部循环的第三次迭代中，您只访问行1和2。等。您只需要dp矩阵的两行！

更多的是，您从0行创建-1行，从0行创建1，从1行创建2行，等等。

你真的需要保留dp矩阵吗？或者你能用previous_row和current_row吗？只存储两个长度的n行将您的空间减少到O(2n)，这就是O(n)。