模式匹配動態規劃建議

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): 

問題陳述

'

'。'匹配任何單個字符。
'*'匹配零個或多個前面的元素。

匹配應該覆蓋整個輸入字符串（不是部分）。

函數原型應該是：
bool isMatch(const char *s, const char *p)

一些例子：
isMatch（ 「AA」， 「A」）→假
isMatch（ 「AA」， 「AA」）→真
isMatch（ 「AAA」， 「AA」）→假
isMatch（ 「AA」， 「A *」）→真
isMatch（ 「AA」， 「* 」）→真
isMatch（「 AB」， 「。*」）→true
isMatch（「aab」 「C * A * B」）→真

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，...）。交換後，該表將逐列填充（第一列，然後是2,3 ...）。

該算法的思想保持不變，因爲table中的每個元素都是通過上一列或多行中的元素定義的---您已計算的元素是否按行或逐列進行計算。

詳細地說，table[j][i]通過前一列table[j-1][i-1]的對角元素定義;或前一行和/或列table[j-2][i],table[j-1][i]和/或table[j][i-1]中的元素。

因此，性能交換後是相同的。在兩個版本中，每個table元素的計算都需要一個恆定的時間。構建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] or table[0][j]相當於table[1][j] = table[0][j]。

對於p[-1]，請注意，您只能在if-聲明中訪問它，此時p[0] = *（對匹配沒有意義）。 p[-1]的值不重要，因爲它不會影響table[i][j]的值。要看到這個結果：如果if -statement的結果恰好是True，我們知道table[1][0]最初是False，所以table[1][1],table[1][2]，...也必須是False。換句話說，p[0] = *不會匹配任何字符串。