題目：請實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包含 .和* 的正則表達(dá)式。模式中的字符.表示任意一個(gè)字符督禽，而 *表示它前面的字符可以出現(xiàn)任意次（含0次）耐齐。在本題中，匹配是指字符串的所有字符匹配整個(gè)模式评架。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配炕泳，但與模式"aa.a"及"ab*a"均不匹配纵诞。
分析：這道題的核心其實(shí)在于分析
'*', 對于'.'來說，它和任意字符都匹配培遵，可把其當(dāng)做普通字符浙芙。對于'*'的分析，我們要進(jìn)行分情況討論籽腕，當(dāng)所有的情況都搞清楚了以后茁裙，就可以寫代碼了。
當(dāng)Patttern第二個(gè)字符不是
*時(shí)节仿，情況簡單：
如果字符串的第一個(gè)字符和模式中的第一個(gè)字符匹配晤锥，那么在字符串和模式上都向后移動一個(gè)字符，然后匹配剩余字符串和模式廊宪。
如果字符串的第一個(gè)字符和模式中的第一個(gè)字符不匹配矾瘾，那么直接返回false。在每輪匹配中箭启，Patttern第二個(gè)字符是
'*'時(shí),情況復(fù)雜：
- 第一個(gè)字符不匹配（除了
'.'與任意字符視作匹配）壕翩，那么這時(shí)'*'只能代表匹配0次，比如''ba''與''a*ba''傅寡，字符串不變放妈，模式向后移動兩個(gè)字符，然后匹配剩余字符串和模式荐操。- 第一個(gè)字符匹配芜抒，那么
'*'可能代表匹配1次，多次托启，0次宅倒，比如"aba"與"a*ba"、 ''aaaba''與''a*ba''屯耸， ''ba''與''b*ba''拐迁。匹配1次時(shí)蹭劈，字符串往后移動一個(gè)字符，模式向后移動2個(gè)字符线召；匹配多次時(shí)铺韧，字符串往后移動一個(gè)字符，模式不變缓淹；
1.遞歸
c code:通過
#include <iostream>
using namespace std;
bool matchCore(char* str, char* pattern);
bool match(char* str, char* pattern)
{
if (str == nullptr || pattern == nullptr)
return false;
return matchCore(str,pattern);
}
bool matchCore(char* str, char* pattern)
{
if (*str == '\0'&&*pattern == '\0')
return true;
if (*str != '\0'&&*pattern == '\0')
return false;
if (*(pattern + 1) == '*')//復(fù)雜情況
{
if (*pattern == *str || (*pattern == '.' && *str != '\0'))
{
//分別表示匹配1次,多次,0次
return matchCore(str + 1, pattern + 2) || matchCore(str + 1, pattern) || matchCore(str, pattern + 2);
}
else
return matchCore(str, pattern + 2);//表示匹配0次,跳過pattern‘*’
}
if (*pattern == *str || (*pattern == '.' && *str != '\0'))//簡單情況
return matchCore(str + 1, pattern + 1);
return false;//所有情況都不滿足
}
int main() {
char str[20];
char pattern[20];
cin>>str;
cin>>pattern;
if (match(str, pattern))
cout << "match" << endl;
else
cout << "not match" << endl;
return 0;
}
c++ code遞歸法:
- leetcode 上超出時(shí)間限制 然而上述的c code可以通過
- 同樣的算法為甚c++超時(shí)哈打，char*比string類更加近原生層（聽說STL除外，大部分c比c++快）
class Solution {
public:
bool isMatch(string s, string p) {
if (s.empty() && p.empty())
return true;
return match(s, 0, p, 0);
}
bool match(string s, int sIndex, string p, int pIndex){
if (sIndex == (s.length()) && pIndex == (p.length()))//遞歸結(jié)束的條件
return true;
if (p[pIndex + 1] == '*'){ //復(fù)雜情況
if (p[pIndex] == s[sIndex] || (p[pIndex] == '.'&&sIndex <= (s.length() - 1)))
return match(s, sIndex, p, pIndex + 2) || match(s, sIndex + 1, p, pIndex + 2) || match(s, sIndex + 1, p, pIndex);
else
return match(s,sIndex,p,pIndex+2);
}
if (p[pIndex] == s[sIndex] || (p[pIndex] == '.'&&sIndex <=(s.length() - 1))) //簡單情況
return match(s, sIndex + 1, p, pIndex + 1);
return false;
}
};
2.動態(tài)規(guī)劃：
首先我們建立了一個(gè) m*n 的二維dp矩陣割卖，其中m表示匹配模式字符串 p 的長度前酿，n表示待匹配字符串 s 的長度患雏。則 dp[i][j] 表示子字符串 p[:i] 和s[:j](均包含i和j)是否匹配(true/false)鹏溯。假設(shè)目前已知 dp[i][j-1] 及其前面的所有情況的匹配關(guān)系，那么要求dp[i][j]通過動態(tài)規(guī)劃的遞推關(guān)系如下：
1. 假如 p[i] == '.'淹仑，則dp[i][j] = dp[i-1][j-1]
2. 假如 p[i] == letter(a-zA-Z)丙挽，則dp[i][j] = dp[i-1][j-1] && (p[i]==s[j])
3. 假如 p[i] == '*',則 dp[i][j] = dp[i-2][j] ||
dp[i-1][j] ||
(dp[i][j-1] && (p[i-1] == s[j]))
上面的1,2 均比較好理解，關(guān)鍵是出現(xiàn) *時(shí)要分三種情況討論匀借，分別是 * 匹配了0個(gè)颜阐，1個(gè)，和若干個(gè)前一字符吓肋。假如匹配了0個(gè)前一字符凳怨，那么當(dāng)前位置的匹配結(jié)果與dp[i-2][j]相同；匹配了1個(gè)前一字符是鬼，則當(dāng)前位置的匹配結(jié)果與 dp[i-1][j]相同肤舞；關(guān)鍵是假如匹配了多個(gè)前一字符，該如何判斷均蜜，此時(shí)我們無法知道到底匹配了多少個(gè)前一字符李剖，但是換個(gè)角度去想這個(gè)問題，假如匹配了多個(gè)前一字符囤耳，那么前一字符要與當(dāng)前的s[j]匹配（p[i-1]==s[j] 或 p[i-1]=’.’）篙顺，此時(shí)要想匹配成功(dp[i][j]為true)，則當(dāng)前的匹配串(p[:i])必須能夠匹配s[:j-1],也就是dp[i][j-1]為true充择。對于這三種情況出現(xiàn)任意一種均可認(rèn)為匹配德玫，因此取或操作。
在具體實(shí)現(xiàn)中還要注意數(shù)組越界的問題椎麦，可以看到上面出現(xiàn)了 i-1化焕，j-1，i-2的下標(biāo)铃剔，那么在實(shí)現(xiàn)的時(shí)候要在原二維矩陣中各增加一行和一列撒桨，表示第0個(gè)字符也就是空字符從而避免了i-1的越界查刻；同時(shí)只有在遇到*時(shí)才會出現(xiàn)i-2的下標(biāo)，且這種情況下只有當(dāng)*出現(xiàn)在匹配串第一個(gè)的時(shí)候才會越界凤类，而當(dāng)*出現(xiàn)在匹配串的第一個(gè)字符的時(shí)候表示為空字符串穗泵，除了待匹配字符串為空時(shí)一律為false。
C++ 動態(tài)開辟二維數(shù)組
- vector<vector<bool>>dp(m,vector<bool>(n));
bool **dp=NULL; dp = new bool *[m]; for (int i = 0; i < m; i++) { dp[i] = new bool[n]; }
c++ code : 8ms
class Solution {
public:
bool isMatch(string s, string p) {
int m = p.length() + 1; int n = s.length() + 1;
//vector<vector<bool>>dp(m,vector<bool>(n));
bool **dp=NULL;
dp = new bool *[m];
for (int i = 0; i < m; i++)
{
dp[i] = new bool[n];
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == 0)//初始化
{
if (j == 0)dp[i][j] = true;
else dp[i][j] = false;
}
else if (j == 0)
{//i只可能是1開始
if (p[i - 1] != '*')dp[i][j] = false;
else dp[i][j] = dp[i - 1][j] || dp[i - 2][j];////p第一個(gè)是*的谜疤，s第一個(gè)是空佃延，短路操作不會越界，所以不能調(diào)換夷磕，細(xì)節(jié)
}
else
{
if (p[i - 1] == '.')dp[i][j] = dp[i - 1][j - 1];
else if (p[i - 1] == '*')
{
if (i == 1)dp[i][j] = false; //第一個(gè)是*的其他情況
else dp[i][j] = dp[i - 2][j]
|| dp[i - 1][j]
|| ((p[i-2]=='.'||p[i-2]==s[j-1])&&dp[i][j - 1]);
}
else dp[i][j] = ((s[j - 1] == p[i - 1] )&& dp[i - 1][j - 1]);
}
}
}
return dp[m - 1][n - 1];
}
};
substr
C++關(guān)于 nullptr
參考1：劍指offer書----何海濤
一生不可自決
參考2
