10. 正則表達(dá)式匹配
鏈接: 10. 正則表達(dá)式匹配
給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 ‘.’ 和 ‘*’ 的正則表達(dá)式匹配。
‘.’ 匹配任意單個字符
‘*’ 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。
示例 1：
輸入：s = “aa”, p = “a”
輸出：false
解釋：“a” 無法匹配 “aa” 整個字符串。
示例 2:
輸入：s = “aa”, p = “a*”
輸出：true
解釋：因為 ‘*’ 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 ‘a(chǎn)’。因此，字符串 “aa” 可被視為 ‘a(chǎn)’ 重復(fù)了一次。
示例 3：
輸入：s = “ab”, p = “."
輸出：true
解釋：".” 表示可匹配零個或多個（‘*’）任意字符（‘.’）。
1.狀態(tài)表示*
dp[i][j] 表?：字符串 p 的 [0, j] 區(qū)間和字符串 s 的 [0, i] 區(qū)間是否可以匹配
2.狀態(tài)轉(zhuǎn)移方程
?規(guī)矩，根據(jù)最后?個位置的元素，結(jié)合題?要求，分情況討論：
- i. 當(dāng) s[i] == p[j] 或 p[j] == '. ’ 的時候，此時兩個字符串匹配上了當(dāng)前的?個字符，只能從 dp[i - 1][j - 1] 中看當(dāng)前字符前?的兩個?串是否匹配。只能繼承上個狀態(tài)中的匹配結(jié)果， dp[i][j] = dp[i][j - 1] ；
- ii. 當(dāng) p[j] == ‘*’ 的時候，此時匹配策略有兩種選擇：
? ?種選擇是： * 匹配空字符串，此時相當(dāng)于它匹配了?個寂寞，直接繼承狀態(tài) dp[i] [j - 1] ，此時 dp[i][j] = dp[i][j -1] ；
? 另?種選擇是： * 向前匹配 1 ~ n 個字符，直?匹配上整個 s1 串。此時相當(dāng)于從 dp[k][j - 1] (0 <= k <= i) 中所有匹配情況中，選擇性繼承可以成功的情況。此時 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ； - iii. 當(dāng) p[j] 不是特殊字符，且不與 s[i] 相等時，?法匹配。 三種情況加起來，就是所有可能的匹配結(jié)果。
綜上所述，狀態(tài)轉(zhuǎn)移?程為：
? 當(dāng) s[i] == p[j] 或 p[j] == ‘?’ 時： dp[i][j] = dp[i][j - 1] ；
? 當(dāng) p[j] == ‘*’ 時，有多種情況需要討論： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；
3. 初始化
由于 dp 數(shù)組的值設(shè)置為是否匹配，為了不與答案值混淆，我們需要將整個數(shù)組初始化為false 。
由于需要?到前??和前?列的狀態(tài)，我們初始化第??、第?列即可。
dp[0][0] 表?兩個空串能否匹配，答案是顯然的，初始化為 true 。
第??表? s 是?個空串， p 串和空串只有?種匹配可能，即 p 串全部字符表?為"任?字符+*"，此時也相當(dāng)于空串匹配上空串。所以，我們可以遍歷 p 串，把所有前導(dǎo)為"任?字符+"的 p ?串和空串的 dp 值設(shè)為 true 。
第?列表? p 是?個空串，不可能匹配上 s 串，跟隨數(shù)組初始化即可
4. 填表順序
根據(jù)「狀態(tài)轉(zhuǎn)移?程」得：從上往下填寫每??，每??從左往右
5. 返回值
返回 dp[m][n]
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-714326.html
bool isMatch(string s, string p) {
int n=s.size();
int m=p.size();
//表示的是 s串中0~i 位置的子串，能否于 p串 0~j 上完全匹配
vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
//初始化
dp[0][0]=true;
for(int i=2;i<=m;i+=2)//初始化有坑
{
if(p[i-1]=='*') dp[0][i]=1;
else break;
}
//填表
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i-1]==p[j-1]||p[j-1]=='.')
{
dp[i][j]=dp[i-1][j-1];
}
if(p[j-1]=='*')
{
if(p[j-2]=='.')
{
dp[i][j]=dp[i][j-2]||dp[i-1][j];
}
else
{
if(p[j-2]==s[i-1])//相等的時候，
dp[i][j]=dp[i][j-2]||dp[i-1][j];
//當(dāng)不相等的時候，也需要考慮匹配空串的情況
else dp[i][j]=dp[i][j-2];
}
}
}
}
return dp[n][m];
}
97. 交錯字符串
鏈接: 97. 交錯字符串
給定三個字符串 s1、s2、s3，請你幫忙驗證 s3 是否是由 s1 和 s2 交錯 組成的。
兩個字符串 s 和 t 交錯 的定義與過程如下，其中每個字符串都會被分割成若干 非空 子字符串：
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交錯 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味著字符串 a 和 b 連接。
示例 2：
輸入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
輸出：false
示例 3：
輸入：s1 = “”, s2 = “”, s3 = “”
輸出：true
1.狀態(tài)表示*
dp[i][j] 表?字符串 s1 中 [1, i] 區(qū)間內(nèi)的字符串以及 s2 中 [1, j] 區(qū)間內(nèi)的字符串，能否拼接成 s3 中 [1, i + j] 區(qū)間內(nèi)的字符串。
2.狀態(tài)轉(zhuǎn)移方程
先分析?下題?，題?中交錯后的字符串為 s1 + t1 + s2 + t2 + s3 + t3… ，看
似?個 s ?個 t 。實際上 s1 能夠拆分成更?的?個字符，進(jìn)?可以細(xì)化成 s1 + s2 +s3 + t1 + t2 + s4… 。
也就是說，并不是前?個?了 s 的?串，后?個必須要? t 的?串。這?點理解，對我們的狀態(tài)轉(zhuǎn)移很重要。
繼續(xù)根據(jù)兩個區(qū)間上「最后?個位置的字符」，結(jié)合題?的要求，來進(jìn)?「分類討論」：
- i. 當(dāng) s3[i + j] = s1[i] 的時候，說明交錯后的字符串的最后?個字符和 s1 的最后?個字符匹配了。那么整個字符串能否交錯組成，變成： s1 中[1, i - 1] 區(qū)間上的字符串以及 s2 中 [1, j] 區(qū)間上的字符串，能夠交 錯形成 s3 中 [1, i + j - 1] 區(qū)間上的字符串，也就是 dp[i - 1][j] ； 此時
dp[i][j] = dp[i - 1][j] - ii. 當(dāng) s3[i + j] = s2[j] 的時候，說明交錯后的字符串的最后?個字符和 s2 的最后 ?個字符匹配了。那么整個字符串能否交錯組成，變成： s1 中 [1, i] 區(qū)間上的字符串以及 s2 中 [1, j - 1] 區(qū)間上的字符串，能夠交 錯形成 s3 中 [1, i + j - 1] 區(qū)間上的字符串，也就是dp[i][j - 1] ；
- iii. 當(dāng)兩者的末尾都不等于 s3 最后?個位置的字符時，說明不可能是兩者的交錯字符串。
上述三種情況下，只要有?個情況下能夠交錯組成?標(biāo)串，就可以返回 true 。因此，我們可以定義狀態(tài)轉(zhuǎn)移為：dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j])|| (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1])
3. 初始化
于?到 i - 1 , j - 1 位置的值，因此需要初始化「第?個位置」以及「第??」和「第?列」。
第?個位置：
dp[0][0] = true ，因為空串+空串能夠構(gòu)成?個空串。
第??：
第??表? s1 是?個空串，我們只?考慮 s2 即可。因此狀態(tài)轉(zhuǎn)移之和 s2 有關(guān)：
dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1] ， j 從 1 到 n
第?列：
第?列表? s2 是?個空串，我們只?考慮 s1 即可。因此狀態(tài)轉(zhuǎn)移之和 s1 有關(guān)：
dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0] ， i 從 1 到 m
4. 填表順序
根據(jù)「狀態(tài)轉(zhuǎn)移?程」得：從上往下填寫每??，每??從左往右
5. 返回值
返回 dp[m][n]
代碼：
bool isInterleave(string s1, string s2, string s3) {
int n=s1.size();
int m=s2.size();
if(m+n!=s3.size()) return false;
s1=" "+s1;
s2=" "+s2;
s3=" "+s3;
//表示的是s1中前i位置的和s2中前j位置能否和s3中前 i+j 位置進(jìn)行組成
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
dp[0][0]=true;
for(int i=1;i<=m;i++)
{
if(s2[i]==s3[i]) dp[0][i]=true;
else break;
}
for(int j=1;j<=n;j++)
{
if(s1[j]==s3[j]) dp[j][0]=true;
else break;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i]==s3[i+j]&&dp[i-1][j])
{
dp[i][j]=true;
}
if(s2[j]==s3[i+j]&&dp[i][j-1])
{
dp[i][j]=true;
}
}
}
return dp[n][m];
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-714326.html
到了這里，關(guān)于【面試算法——動態(tài)規(guī)劃 21】正則表達(dá)式匹配（hard）&& 交錯字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
