主題
題目連結：
題目意譯：
給定一個數字字串 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] 之值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
