文章目錄

• 題目描述
• 思路 && 代碼
• • • 二刷

打卡第十二天～

題目描述

• 拖了超級久的一道題= =，懶得看正則表達式，但是其實和正則表達式相關(guān)的地方也不多
  
  

思路 && 代碼

• 參照這篇題解寫的，dalao屬實萬物皆可動態(tài)規(guī)劃。
• 主要是分情況（見代碼注釋的Case），主要是：
• 空正則（正則表達式為 “” )
• 非空正則：
  a. 不是 ‘??’ 的情況
  b. 是 ‘??’ 的情況：重復 0 次的情況 && 重復的情況
• |= 的考慮：2.a 和 2.b，只要滿足其中一個即可
• ‘.'的考慮：在這個代碼里，實際上只是相當于一個萬用符
• 建議還是得動手畫一遍表格來填，幫助理解。

class Solution {public boolean isMatch(String s, String p) {// init int m = s.length();int n = p.length();char[] arr1 = s.toCharArray();char[] arr2 = p.toCharArray();// dp[i][j] 代表 s 的前 i 個和 p 的前 j 個能否匹配boolean[][] dp = new boolean[m + 1][n + 1];// dp 過程for(int i = 0; i <= m; i++) {for(int j = 0; j <= n; j++) {// Case 1: 空正則if(j == 0) {dp[i][j] = (i == 0);}// Case 2: 非空正則else {// Case 2.1：不是'*'if(arr2[j - 1] != '*') {// 相等 or 為'.'的情況，直接看左上角的最優(yōu)子結(jié)構(gòu)if(i > 0 && (arr1[i - 1] == arr2[j - 1] || arr2[j - 1] == '.')) {dp[i][j] = dp[i - 1][j - 1];}}// Case 2.2：是'*'（最重要的部分）else {// Case 2.2.1：不看if(j >= 2) {// 重復0次，相當于直接砍掉最后兩個字符dp[i][j] = dp[i][j - 2];}// Case 2.2.2：看if(i >= 1 && j >= 2 && (arr1[i - 1] == arr2[j - 2] || arr2[j - 2] == '.')) {// 多重復一次，和 s 串前移一位的結(jié)果一樣// 為什么 |= ，相當于判斷兩次，只要有一次 true 就算 truedp[i][j] |= dp[i - 1][j];}}}}}return dp[m][n];} }

二刷

• 倒沒想象中那么惡心了，主要還是分好情況，然后再考慮如何dp
• 注意狀態(tài)轉(zhuǎn)移方程用到的最優(yōu)子結(jié)構(gòu)。

class Solution {public boolean isMatch(String s, String p) {boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];for(int i = 0; i <= s.length(); i++) {for(int j = 0; j <= p.length(); j++) {if(j == 0) {dp[i][j] = (i == 0);continue;}// Case 1: 沒碰到 * 的情況if(p.charAt(j - 1) != '*') {if(i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {dp[i][j] = dp[i - 1][j - 1];}}// Case 2: 碰到 * 的情況else {// Case 2.1：不用 * if(j >= 2) {dp[i][j] = dp[i][j - 2];}// Case 2.2：用 *if(i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {// 重復了一次，說明可以套用上一個 i 的結(jié)果。dp[i][j] |= dp[i - 1][j];}}}}return dp[s.length()][p.length()];} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指Offer 19. 正则表达式匹配（Java、动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。