Regular Expression Matching
原題鏈接Regular Expression Matching
意思是模擬正則表達式的. *操作，判斷給定的目標字符串p是否匹配源字符串s。
規則
- ‘.’匹配任意一個字符
- ‘*’匹配前一個字符0次或者多次，即可以刪除它前面的字符
注：例子中isMatch(“ab”, “.“) == true說明”.“可以匹配的字符可以是任意組合，比如說此題中”.”匹配成”a”，那么因為 ” * ” 的前面是”.”，說明” * “可以匹配任意字符，不是說必須是前面”.”匹配的字符，也就是說”*”匹配的可以不是”.”匹配的”a”
假設s的長度為s_len，p的長度為p_len，那么可以分成比較s[0]和p[0]，以及s[1 : s_len)和p[1 : p_len)，再簡化一點，如果p中沒有” * “，可能會有” . “時
分析題目時可以分解成幾種情況，
(s[0] == p[0]) || (p[0] == ‘.’)。此時只需要比較s[1 : s_len)和p[1 : p_len)是否相等，遞歸即可實現(s[0] != p[0]) && (p[0] != ‘.’)。此時無需繼續比較，返回false
如果p中有” * “，那么情況增多
((s[0] == p[0]) || (p[0] == ‘.’)) &&p[1] != ‘*’；此時和上面情況相同，比較下一個位置即可((s[0] == p[0]) || (p[0] == ‘.’)) && p[1] == ‘‘；根據” “的規則，p[0]可以被刪掉然后從p[2]開始和s[0]比較，這是一種情況。另一種是重復p[0]多次，多次的意思是p[0]后面可能有多個”p[0] * p[0] * p[0] * “，而模擬多次重復最好的方法就是不改變p的索引，仍然從p[0]開始比較s的下一個位置s[1]。((s[0] != p[0]) && (p[0] != ‘.’)) && p[1] == ‘*’；顯然直接刪除p[0]，從p[2]開始比較s[0]((s[0] != p[0]) && (p[0] != ‘.’)) && p[1] != ‘*’；直接return fales，沒得比了，當前這個位置就匹配不了
所以很多時候把所有情況列出來會很好的理清思路，這種當前狀態可能會影響后續狀態的問題是動態規劃的典型問題，所以直接套用動態規劃即可。
需要注意的就是一些邊界條件，比方說i == s.size()的情況和j == p.size()的情況，又或者是j + 1 >= p.size()的情況，這種情況p[j + 1]不存在，就沒辦法判斷后面的字符是否是’*’。
首先是遞歸的動態規劃，dp[i][j]的意思是s[i : s_len)是否和p[j : p_len)匹配，遞歸時需要有三種狀態
1，true0，false-1，還沒有被考慮
class Solution {
public:
bool isMatch(
string s,
string p) {
std::
vector<std::vector<int> > dp(s.size() +
1,
std::
vector<int>(p.size() +
1, -
1));
return judge_match(
0,
0, s, p, dp) ==
1;}
private:
int judge_match(
int i,
int j,
const std::
string& s,
const std::
string& p,
std::
vector<std::vector<int> >& dp){
if(dp[i][j] != -
1)
return dp[i][j];
if(j >= p.size() && i >= s.size())
return 1;
else if(j >= p.size() && i < s.size())
return 0;
bool ans;
bool first_match = (i < s.size()) && ((s[i] == p[j]) || (p[j] ==
'.'));
if(j +
1 < p.size() && p[j +
1] ==
'*')ans = (first_match && judge_match(i +
1, j, s, p, dp) ==
1) || (judge_match(i, j +
2, s, p, dp) ==
1);
elseans = (first_match && judge_match(i +
1, j +
1, s, p, dp) ==
1);dp[i][j] = ans ?
1 :
0;
return dp[i][j];}
};
然后是非遞歸的，非遞歸的動態規劃很重要，真…的…很重要，
逐層向目標接近，有個選擇兩層for循環的界限的技巧，初始時是離目標最遠的狀態
比如說如果目標是dp[0][0]，那么初始時就是dp[s_len - 1][p_len - 1]，如果目標是dp[0][p_len]，那么初始時就是dp[s_len][0]
但是，需要考慮邊界情況，比如說本題就需要考慮dp[s_len][0],dp[s_len][1]…dp[s_len][p_len - 1]，原因在遞歸中也體現了，就是如果s到了尾端而p沒有到，也是有可能匹配成功的（p后面的字符全可以刪除時），所以初始時是dp[s_len][p_len - 1]
class Solution {
public:
bool isMatch(
string s,
string p) {
std::
vector<std::vector<bool> > dp(s.size() +
1,
std::
vector<bool>(p.size() +
1,
false));dp[s.size()][p.size()] =
true;
for(
int i = s.size(); i >=
0; --i){
for(
int j = p.size() -
1; j >=
0; --j){
bool first_match = (i < s.size()) && (s[i] == p[j] || p[j] ==
'.');
if(j +
1 < p.size() && p[j +
1] ==
'*')dp[i][j] = (first_match && dp[i +
1][j]) || (dp[i][j +
2]);
elsedp[i][j] = (first_match && dp[i +
1][j +
1]);}}
return dp[
0][
0];}
};
Wildcard Matching
原題鏈接Wildcard Matching
這道題和上面的基本一樣了，不同點就是’*’的規則有改變，代碼如下
沒什么特別的，也分遞歸和非遞歸，判斷的時候多了一個條件，就是’*’可以表示空字符
class Solution {
public:
bool isMatch(
string s,
string p) {
std::
vector<std::vector<bool> > dp(s.size() +
1,
std::
vector<bool>(p.size() +
1,
false));dp[s.size()][p.size()] =
true;
for(
int i = s.size(); i >=
0; --i){
for(
int j = p.size() -
1; j >=
0; --j){
bool first_match = (i < s.size()) && (s[i] == p[j] || p[j] ==
'?' || p[j] ==
'*');
if(p[j] ==
'*')dp[i][j] = (first_match && dp[i +
1][j]) || (first_match && dp[i +
1][j +
1]) || (dp[i][j +
1]);
elsedp[i][j] = (first_match && dp[i +
1][j +
1]);}}
return dp[
0][
0];}
};
總結
以上是生活随笔為你收集整理的每天一道LeetCode-----只可能有'.'和'*'的字符串正则匹配的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
