10 Regular Expression Matching 正則表達(dá)式匹配
Description:
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example:
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
題目描述:
給你一個字符串 s 和一個字符規(guī)律 p缔逛，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達(dá)式匹配谱轨。
'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配撮抓，是要涵蓋 整個 字符串 s的，而不是部分字符串隆圆。
說明：
s 可能為空抹凳，且只包含從 a-z 的小寫字母漂彤。
p 可能為空鸯匹，且只包含從 a-z 的小寫字母坊饶，以及字符 . 和 *。
示例 :
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串殴蓬。
示例 2:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'匿级。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次染厅。
示例 3:
輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'）痘绎。
示例 4:
輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復(fù)一次肖粮。因此可以匹配字符串 "aab"孤页。
示例 5:
輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false
思路:
- 雙字符串匹配, 會產(chǎn)生大量子問題, 可以用動態(tài)規(guī)劃解決
- 首先定義 dp[i][j]表示 s[:i]和p[:j]匹配
- 從 dp[i - 1][j - 1]出發(fā), 觀察 s[i]和 p[j]
3.1 最簡單的情況, s[i] == p[j], 則 dp[i][j] = dp[i - 1][j - 1]
3.2 若 p[j] == ".", 也可以直接匹配, 則dp[i][j] = dp[i - 1][j - 1]
3.3 若 p[j] == "*", 要匹配之前的字符 0個或多個, 這里又可以分兩種情況, 一種是 p[j - 1] == s[i](p[j - 1] == "."也是歸類到這一種), 那么可以匹配, 有dp[i][j] = dp[i - 1][j - 1], 另一種是 p[j - 1] != s[i], 這里可以看是否是 0個匹配, 要看 dp[i][j - 2], 所以有dp[i][j] = dp[i][j - 2]
時間復(fù)雜度O(mn), 空間復(fù)雜度O(mn), n, m分別為 s和 p的長度
注意到這里只使用了 dp兩行相鄰的, 可以將空間復(fù)雜度減小到 O(m)
代碼:
C++:
class Solution
{
public:
bool isMatch(string s, string p)
{
int n = s.size(), m = p.size();
bool dp[n + 1][m + 1];
for (int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) dp[i][j] = false;
dp[0][0] = true;
for (int i = 2; i <= m; i++) if (p[i - 1] == '*') dp[0][i] = dp[0][i - 2];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s[i - 1] == p[j - 1] or p[j - 1] == '.') dp[i][j] = dp[i - 1][j - 1];
if (p[j - 1] == '*') if (j > 1) dp[i][j] = ((p[j - 2] == s[i - 1] or p[j - 2] == '.') and dp[i - 1][j]) or dp[i][j - 2];
}
}
return dp[n][m];
}
};
Java:
class Solution {
public boolean isMatch(String s, String p) {
return s.matches(p);
}
}
Python:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
return re.match(p + '$', s)
