處理模式匹配問題。併發布詳細的問題陳述和代碼。代碼正在工作。在下面的實現中,它在外部循環中循環模式,然後在內部循環中匹配源字符串 - 以構建二維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]
在此先感謝, 林
爲什麼你不使用正則表達式? – fgoettel
@deloz,這只是一個DP編程難題。您的建議在我的原始問題上表示讚賞。 :) –