LeetCode解析------10.正規表達式比對-動态規劃

題目：

給你一個字元串 s 和一個字元規律 p，請你來實作一個支援 ‘.’ 和 ‘*’ 的正規表達式比對。

‘.’ 比對任意單個字元

‘*’ 比對零個或多個前面的那一個元素

所謂比對，是要涵蓋 整個 字元串 s的，而不是部分字元串。

說明:

s 可能為空，且隻包含從 a-z 的小寫字母。

p 可能為空，且隻包含從 a-z 的小寫字母，以及字元 . 和 *。

示例 1:

輸入: s = “aa” p = “a”

輸出: false

解釋: “a” 無法比對 “aa” 整個字元串。

示例 2:

輸入: s = “aa” p = “a*”

輸出: true

解釋: 因為 ‘*’ 代表可以比對零個或多個前面的那一個元素,

在這裡前面的元素就是 ‘a’。是以，字元串 “aa” 可被視為 ‘a’ 重複了一次。

示例 3:

輸入: s = “ab” p = ". * "

輸出: true

解釋: "." 表示可比對零個或多個（’’）任意字元（’.’）。

示例 4:

輸入: s = “aab” p = “c * a * b”

輸出: true

解釋: 因為 ‘*’ 表示零個或多個，這裡 ‘c’ 為 0 個,

‘a’ 被重複一次。是以可以比對字元串 “aab”。

示例 5:

輸入: s = “mississippi” p = “mis * is * p * .”

輸出: false

簡單介紹：

題目：正規表達式比對

題目難度：困難

使用語言：JAVA

這道題來自leetcode題庫的動态規劃标簽。

解題思路：

首先看題、分析題意，我們可以明确1個關鍵點：

1.p比對s有哪些情況？

2.如果使用動态規劃dp需要怎樣描述？

既然，我們已經分析出來題目的關鍵任務了，下面我們就可以開始思考實作了。

我們采用算法與資料結構的思路來剖析一下這題

資料結構：

要實作對資料的操作，我們要先明确存儲資料的資料結構。

該題的資料結構的作用：

1.二維數組dp。dp[i][j]表示p的前j個字元可以比對s的前i個字元

算法：

既然明确了我們的資料結構，我們就可以開始我們的算法分析了。

1.第一步，初始化工作（為dp申請空間）。

2.第二步，根據比對情況不同，分情況處理。

代碼部分：

public class Solution {
    public boolean isMatch(String s, String p) {
        //初始化工作
        if(s==null||p==null)
            return false;
        //dp[i][j]表示p的前j個字元可以比對s的前i個字元
        boolean [][]dp=new boolean[s.length()+1][p.length()+1];
        
        //開始比對
        dp[0][0]=true;
        for(int i=0;i<p.length();i++){
            if(p.charAt(i)=='*'&&dp[0][i-1])
                dp[0][i+1]=true;//p的i+1個字元可以去掉
        }

        for(int i=0;i<s.length();i++){
            for(int j=0;j<p.length();j++){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){//字元比對或字元是萬能字元（'.'）
                    dp[i+1][j+1]=dp[i][j];
                }
                    
                if(p.charAt(j)=='*'){
                    if(s.charAt(i)!=p.charAt(j-1)&&p.charAt(j-1)!='.'){//字元無法比對且字元不是萬能字元（'.'）
                        dp[i+1][j+1]=dp[i+1][j-1];//去掉p的1個字母和1個*
                    }
                    else{
                        dp[i+1][j+1]=dp[i][j+1]||dp[i+1][j]||dp[i+1][j-1];
                        //dp[i][j+1]:p的j+1字元可以比對s的i個字元。如s和p分别為abc和abc*（*去掉）
                        //dp[i+1][j]:p的j字元可以比對s的i+1個字元。如s和p分别為abccc和abc*（*為2個c）
                        //dp[i+1][j-1]:p的j+1字元可以比對s的i個字元。如s和p分别為abc和abcc*（*為0個c）

                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

           

時間、空間複雜度：

結語：

晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！晚安！