最近正好在學(xué)編譯原理,和計(jì)算理論,正則表達(dá)式接觸的也比較多.
題目:
請實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包含'. '和''的正則表達(dá)式胚嘲。
模式中的字符'.'表示任意一個(gè)字符滚澜，而''表示它前面的字符可以出現(xiàn)任意次（含0次）界赔。
在本題中中跌，匹配是指字符串的所有字符匹配整個(gè)模式。
例如发钝，字符串"aaa"與模式"a.a"和"abaca"匹配顿涣，但與"aa.a"和"ab*a"均不匹配波闹。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有酝豪。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處精堕。
其實(shí)是一個(gè)較為簡單的正則表達(dá)式,簡單來說正則表達(dá)式就是一種模式,用來表示各種符合相應(yīng)特性的字符串,題目中只有兩種特殊情況
- '.' 表示任意字符
- '*'表示閉包,代表前一個(gè)字符可以取0或無數(shù)次
難點(diǎn)就在于這個(gè)* 有可能是一次,有可能0次,也有可能是多次,所以整個(gè)題目終點(diǎn)都在處理*符號(hào).
一開始很容易就對兩個(gè)字符串
1.s代表輸入字符串
2.p代表模式字符串
使用兩個(gè)指針依次匹配是否相等,或者等于'.'
在遇到'*'的再進(jìn)行特殊的處理,
但寫著寫著發(fā)現(xiàn)'*'在不同的位置需要判斷的情況過于復(fù)雜,沒有辦法一個(gè)一個(gè)判斷很好的覆蓋所有的情況,所以沒有規(guī)劃的判斷會(huì)導(dǎo)致代碼越來越混亂,太多的ifelse到最后我也沒有調(diào)出正確結(jié)果.
于是借鑒了題解提供的動(dòng)態(tài)規(guī)劃的思路:
我們首先要構(gòu)建一個(gè)二維數(shù)組,boolean dp[n+1][m+1]
其中n是s字符串的長度,m是p字符串的長度
而dp[i][j]所代表的含義是,s的前i個(gè)字符與p前j個(gè)字符的模式是否能夠匹配
具體一點(diǎn)來說是s的[0,i) 和p的[0,j) 是否匹配,不包含第i和j.
動(dòng)態(tài)規(guī)劃就像是歸納假設(shè)一樣最重要的兩步
1.確定初始狀態(tài)
首先,考慮字符串為null的情況,當(dāng)s或者p為null的時(shí)候,我們直接認(rèn)為是不匹配的
if(s==null||p==null){
return false;
}
其次,若s和p長度為0或者說為空的時(shí)候,我們認(rèn)為
dp[0][0] =true ;
2.確定遞推關(guān)系
我們無需關(guān)心具體哪一個(gè)位置,遞推關(guān)系只要關(guān)注該結(jié)果是如何通過上一步推導(dǎo)的
我們關(guān)心dp[i][j] 則需要根據(jù)s.charAt(i-1) p.charAt(j-1)的關(guān)系來進(jìn)行判斷,這也就是題目匹配的最主要的邏輯部分.我們分類討論各種情況
(此處i-1 j-1仍是因?yàn)閐p[i][j]的定義是左閉右開的原因)
根據(jù)題目,字符有a-z '.' '*' 三種
1)當(dāng)s.charAt(i-1)==p.charAt(j-1)
也就是當(dāng)前所在的位置的兩個(gè)字符相等,可以認(rèn)為
dp[i][j]=dp[i-1][j-1]
如果兩個(gè)字符不相等的話,又有以下情況
2)當(dāng)p.charAt(j-1)=='.'
由于'.'匹配任意字符,這個(gè)情況與情況1并沒有區(qū)別
dp[i][j]=dp[i-1][j-1]
3)當(dāng)p.charAt(j-1)==''
根據(jù)題目我們知道一定和它前面一個(gè)字符有關(guān),并且他可能代表0個(gè),1個(gè)或者多個(gè),
i) 0個(gè) 由于當(dāng)前的字符與前的字符不匹配,所以我們可以忽略這個(gè)以及前字符.
例如 當(dāng)s=ab p=acb 的時(shí)候, 此時(shí)并不需要匹配c,則把c*視為0個(gè).
這種情況下, 即p.charAt(j-2)!=s.charAt(i-1)
則我們讓
dp[i][j] = dp[i][j-2] (相當(dāng)于去掉p[j-1]和p[j-2])
ii)1個(gè) 由于當(dāng)前的字符與前的字符匹配 且僅需要一個(gè), 我們可以忽略掉號(hào),僅僅做正常的字符匹配就行了 即,p.charAt(j-2)==s.charAt(i-1)
例如 s=ab p=ab*
則dp[i][j]=dp[i][j-1]
iii)多個(gè) 由于當(dāng)前的字符與前的字符匹配 且僅需要多個(gè),
即p.charAt(j-2)==s.charAt(i-1) 且至少p.charAt(j-2)==s.charAt(i-2)
則dp[i][j] = dp[i-1][j] 這代表著如果i-1的串模式是匹配的,那么在輸入一個(gè)相同的字符,將不影響這個(gè)結(jié)果.
例如s=abbb p=ab
具體來說abbb是否匹配ab* 相當(dāng)于abb是否匹配ab* 相當(dāng)于ab是否匹配ab*此時(shí)由前面1個(gè)的情況 則又取決于ab(s)與ab(p)是否匹配.顯然是成立的
最后
s.charAt(i-1)!=p.charAt(j-1) 且p.charAt(j-1)也不是'.'或者'*'的時(shí)候,
則代表模式無法匹配.dp[i][j]=false
代碼示例:
public boolean isMatch(String s, String p) {
\\判斷是否為null
if(s==null||p==null){
return false;
}
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0]=true;\\認(rèn)為兩個(gè)空串匹配
for(int j=2;j<m+1;j++)
{
if(p.charAt(j-1)=='*'&&dp[0][j-2]) {
dp[0][j] = true;
}
}
for(int i = 1;i<n+1;i++){
for(int j = 1;j<m+1;j++){
char a= s.charAt(i-1);\\當(dāng)前s的字符
char b= p.charAt(j-1);\\當(dāng)前p的字符
if(a==b){
dp[i][j]=dp[i-1][j-1];
}
else{
if(b=='.'){
dp[i][j]=dp[i-1][j-1];
}
else if(b=='*'){
if(j>=2){ \\為了保證j-2不會(huì)出錯(cuò),實(shí)際上*不可能前面沒有字符
char c = p.charAt(j-2);
if(c==a||c=='.') { \\字符匹配與.號(hào)匹配情況相同,合并在一起
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; \\只有 p.charAt(j-2)==s.chatAt(i-1)或 p.charAt(j-2)==‘.’才可以讓*取1個(gè)或者多個(gè)字符：
}
dp[i][j] = dp[i][j]||dp[i][j-2];\\上述的結(jié)果或*代表0個(gè)的情況
}
}
else{
dp[i][j]=false;
}
}
}
}
return dp[n][m];
}
