劍指 Offer 19. 正規表達式比對（困難）

思路：

有2種特殊字元：

"*" 和 "."    a*表示0或多個a，.表示可以是任何數

代碼：

class Solution {
    public boolean isMatch(String s, String p) {
		int sLen=s.length();
		int pLen=p.length();
		//比s和p的長度多一行一列
		boolean[][] dp=new boolean[sLen+1][pLen+1];
		//是設為bool值而不是0/1
		dp[0][0]=true;
	
		//初始化首行,每次加偶數次，因為如果偶數位有*，就可以變為0個
		for(int i=2;i<pLen+1;i+=2){
			dp[0][i]=dp[0][i-2]&&p.charAt(i-1)=='*';
		}
		
		//注意邊界
		for(int i=1;i<=sLen;i++){
			for(int j=1;j<=pLen;j++){
				//分是*和不是*的情況
				if(p.charAt(j-1)=='*'){
					dp[i][j]=dp[i][j-2]||dp[i-1][j]&&s.charAt(i-1)==p.charAt(j-2)||dp[i-1][j]&&p.charAt(j-2)=='.';
				}
				else{
					dp[i][j]=dp[i-1][j-1]&&s.charAt(i-1)==p.charAt(j-1)||dp[i-1][j-1]&&p.charAt(j-1)=='.';
					
				}
			}
		}
		
		return dp[sLen][pLen];
		
    }
}
           

分解：

1）轉移方程：

分為2種情況：p[j-1]為*和p[j-1]不為*

    i）p[j-1]='*'：

（1）dp[i][j-2]是否為true，j後退2格，比較是否為true。然後因為j目前是*，可以忽略後面2個，相當于0個

（2）dp[i-1][j]  i後退一格，比較i-1時是否為true。然後比較目前i與前一個j是否相等（s[i-1]=p[j-2]||p[j-2]='.'）

p[j-2]等于'.'時，就相當于與s[i-1]相等了，因為它可以變為任何數

    ii）p[j-1]!='*'：

dp[i-1][j-1]   i與j 都後退一格的情況。如果為true，則比較目前i與j的s和p是否相等

2）此題的dp類型是boolean[][]而不是int[][]

3）dp比s和p多一行一列，建立dp時dp[m+1][n+1]

4）最後傳回的結果是最後一個dp[m][n]（dp[m+1][n+1]就出界了）

5）p[j-1]就代表的p中的第j個字元

複雜度分析：

時間複雜度：O（M*N） m行n列都要周遊到，也就是每一個數

空間複雜度：O（M*N） dp存儲了所有的數的bool類型