python - 模式匹配动态规划的建议

Question

正在处理以下模式匹配问题。并贴出详细的问题陈述和代码。该代码正在运行。在下面的实现中，它在外循环中循环模式，然后在内部循环中匹配源字符串——以构建二维 DP 表。

我的问题是，如果我更改实现，哪个外循环用于匹配源字符串，而内循环用于匹配模式。会有任何性能提升或任何功能缺陷吗？任何关于哪种口味更好或几乎相同的建议都将受到赞赏。

更具体地说，我的意思是从下面更改循环(对循环内容使用类似的逻辑)，

    for i in range(1, len(p) + 1):
        for j in range(1, len(s) + 1):

到，

    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):

问题陈述

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

class Solution(object):

    def isMatch(self, s, p):
        # The DP table and the string s and p use the same indexes i and j, but
        # table[i][j] means the match status between p[:i] and s[:j], i.e.
        # table[0][0] means the match status of two empty strings, and
        # table[1][1] means the match status of p[0] and s[0]. Therefore, when
        # refering to the i-th and the j-th characters of p and s for updating
        # table[i][j], we use p[i - 1] and s[j - 1].

        # Initialize the table with False. The first row is satisfied.
        table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]

        # Update the corner case of matching two empty strings.
        table[0][0] = True

        # Update the corner case of when s is an empty string but p is not.
        # Since each '*' can eliminate the charter before it, the table is
        # vertically updated by the one before previous. [test_symbol_0]
        for i in range(2, len(p) + 1):
            table[i][0] = table[i - 2][0] and p[i - 1] == '*'

        for i in range(1, len(p) + 1):
            for j in range(1, len(s) + 1):
                if p[i - 1] != "*":
                    # Update the table by referring the diagonal element.
                    table[i][j] = table[i - 1][j - 1] and \
                                  (p[i - 1] == s[j - 1] or p[i - 1] == '.')
                else:
                    # Eliminations (referring to the vertical element)
                    # Either refer to the one before previous or the previous.
                    # I.e. * eliminate the previous or count the previous.
                    # [test_symbol_1]
                    table[i][j] = table[i - 2][j] or table[i - 1][j]

                    # Propagations (referring to the horizontal element)
                    # If p's previous one is equal to the current s, with
                    # helps of *, the status can be propagated from the left.
                    # [test_symbol_2]
                    if p[i - 2] == s[j - 1] or p[i - 2] == '.':
                        table[i][j] |= table[i][j - 1]

        return table[-1][-1]

提前致谢，林

Answer 1

如果交换循环，i 将是 s 的索引，而 j 将是 p< 的索引。您需要在循环中的任何地方交换 i 和 j。

    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j - 1] != "*":
                # Update the table by referring the diagonal element.
                table[j][i] = table[j - 1][i - 1] and \
                              (p[j - 1] == s[i - 1] or p[j - 1] == '.')
            else:
                # Eliminations (referring to the vertical element)
                # Either refer to the one before previous or the previous.
                # I.e. * eliminate the previous or count the previous.
                # [test_symbol_1]
                table[j][i] = table[j - 2][i] or table[j - 1][i]

                # Propagations (referring to the horizontal element)
                # If p's previous one is equal to the current s, with
                # helps of *, the status can be propagated from the left.
                # [test_symbol_2]
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    table[j][i] |= table[j][i - 1]

原始算法逐行填充 table(第一行 1，然后是 2、3，...)。交换后，表格将逐列填充(首先是第 1 列，然后是 2、3、...)。

算法的思想保持不变，因为 table 中的每个元素都是通过前一列或行上的元素定义的——不管你是逐行计算的，你已经计算过的元素或逐列。

具体来说，table[j][i]是通过上一列table[j-1][i-1]的对角线元素定义的；或前面行和/或列中的元素 table[j-2][i]、table[j-1][i] 和/或 表[j][i-1].

因此，交换后的性能是一样的。在这两个版本中，table 元素的每次计算都需要一个常数时间。构建表的总时间是O(len(s) * len(p))。

交换后功能也是一样的。基本上，如果原始版本是正确的，那么修改后的版本也是正确的。原始的是否正确是另一回事......

让我们看一下原始版本。乍一看，i = 1 时似乎有两个地方存在索引问题:table[i - 2][j] 和 p[i - 2 ]。

但是，Python 将索引 -1 解释为最后一个元素。因此，table[-1][j] 引用了 table 的最后一行，其中所有元素都是 False。所以，table[1][j] = table[-1][j] 或 table[0][j] 等同于 table[1][j] = table[0 ][j].

对于 p[-1]，请注意，当 p[0] = * 时，您只能在 if 语句中访问它(这对匹配没有意义)。 p[-1] 的值是多少并不重要，因为它不会影响 table[i][j] 的值。看一下:如果 if 语句的结果恰好是 True，我们知道 table[1][0] 最初是False，所以 table[1][1], table[1][2], ... 也必须是 False 。换句话说，p[0] = * 不会匹配任何字符串。