主題

LeetCode - 10. Regular Expression Matching 解題心得

Not In My Back Yard | 2021-04-25 00:00:21 | 巴幣 0 | 人氣 51

題目連結:


題目意譯:
給定一個數字字串 s 以及一個格式 p,實作正規表示法(Regular Expression)之配對以 '.' 和 '*' 為輔,其中:
'.' 配對到任意一個字元。
'*' 配對 0 個或更多的前一個元素。

配對應覆蓋到整個輸入字串(而不是一部分)。

限制:
0 ≦ s.length ≦ 20
0 ≦ p.length ≦ 30
s 只包含小寫英文字母。
p 只包含小寫英文字母、 '.' 以及 '*' 。
保證每個 '*' 前面都會有一個合法字元可用來配對。



範例測資:
範例 1:
輸入: s = "aa", p = "a"
輸出: false
解釋: "a" 沒有配對到整個字串。

範例 2:
輸入: s = "aa", p = "a*"
輸出: true
解釋: '*' 代表 0 次或多次的前一個元素,即 'a'。因此,重複 'a' 兩次便得到了 "aa"。

範例 3:
輸入: s = "ab", p = ".*"
輸出: true
解釋: ".*" 代表「 0 個或多個(*)的任意字元(.)」。

範例 4:
輸入: s = "aab", p = "c*a*b"
輸出: true
解釋: 'c' 可以重複 0 次,'a' 可以重複 2 次。因此其配對了 "aab"。

範例 5:
輸入: s = "mississippi", p = "mis*is*p*."
輸出: false


解題思維:
定義字串 s 之長度為 n 、字串 p 之長度為 m,以及一個陣列 D[i][j] 代表子字串 s[i] ~ s[n - 1] 是否可以與子字串 p[j] ~ p[m - 1] 作配對。因此所求為 D[0][0] ,即 s 是否可以與 p 配對。

將 D[m][n] = true(空字串配對空字串),作為遞迴式初始條件(其他位置預設為 false)。而遞迴式為
當 p[j + 1] 為 '*' 時,D[i][j] =
D[i][j + 2]
(不將 s[i] 與 p[j] 配對)
或是
X 且 D[i + 1][j]
(使用一個 p[j] 與 s[i] 配對,而因為 '*' 之故 p[j] 可以繼續使用)

否則 D[i][j] =
X 且 D[i + 1][j + 1]
(將 p[j] 與 s[i] 配對)
其中 X 為 true,代表 i 不為 m 且 (p[j] 為 '.' 或是 p[j] 等於 s[i])。

因此我們從 i = m 開始跑到 i = 0。對於每個 s[i] 跑一次從 j = n - 1 到 j = 0,然後計算 D[i][j] 之值(根據上述遞迴關係式。因為此時遞迴中所有項次已知,可直接推得 D[i][j])。

跑完後便可得出所求 D[0][0] 之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作