正則表達式匹配

?前言

大家好，我是知識汲取者，歡迎來到我的LeetCode熱題100刷題專欄！

精選 100 道力扣（LeetCode）上最熱門的題目，適合初識算法與數(shù)據(jù)結構的新手和想要在短時間內高效提升的人，熟練掌握這 100 道題，你就已經(jīng)具備了在代碼世界通行的基本能力。在此專欄中，我們將會涵蓋各種類型的算法題目，包括但不限于數(shù)組、鏈表、樹、字典樹、圖、排序、搜索、動態(tài)規(guī)劃等等，并會提供詳細的解題思路以及Java代碼實現(xiàn)。如果你也想刷題，不斷提升自己，就請加入我們吧！QQ群號：827302436。我們共同監(jiān)督打卡，一起學習，一起進步。

博客主頁??：知識汲取者的博客

LeetCode熱題100專欄??：LeetCode熱題100

Gitee地址??：知識汲取者 (aghp) - Gitee.com

Github地址??：Chinafrfq · GitHub

題目來源??：LeetCode 熱題 100 - 學習計劃 - 力扣（LeetCode）全球極客摯愛的技術成長平臺

PS：作者水平有限，如有錯誤或描述不當?shù)牡胤剑瑧┱埣皶r告訴作者，作者將不勝感激

??題目

原題鏈接：10. 正則表達式匹配 - 力扣（LeetCode）

??題解

• 解法一：正則表達式

  這里標記是困難，但是如果使用正則表達式一行代碼就解決了，但是這題的作者可能并不是想要我們使用正則表達式，而是使用動態(tài)規(guī)劃，如果使用動態(tài)規(guī)劃這題難度直接上升幾個等級。所以大家不要為了做題而做題，而是去學習了解更多的算法思路，有時候我們不需要去把一個題給AC了，而是要做到，看到一個題能夠第一時間直到這題考察的內容，應該使用哪種算法策略，畢竟現(xiàn)在AI這么流行，直接把一個題交給AI，他立馬能夠給你解答。

  當然這題使用正則也不賴，也是一種比較優(yōu)秀的解法，但是卻無法鍛煉到我們的邏輯思維，因為太簡單了??正則表達式YYDS

  import java.util.regex.Pattern;
  
  class Solution {
      public boolean isMatch(String s, String p) {
          return Pattern.matches(p, s);
      }
  }
  

  復雜度分析：

  • 時間復雜度：$O(n)$，正則匹配本質是
  • 空間復雜度：$O(1)$

  其中 $n$ 為字符串的長度

• 解法二：動態(tài)規(guī)劃

  本段代碼來自這位大佬的：fomalhaut1998 - 力扣（LeetCode）

  class Solution {
      public boolean isMatch(String s, String p) {
          /*
          dp五部曲:
          設主串s的長度為m,設模式串p的長度為n;其中s只有小寫字母,p有字母/./*
          1.狀態(tài)定義:dp[i][j]為考慮s[0,i-1]與p[0,j-1]是否能匹配上,能匹配上就為true
          2.狀態(tài)轉移:若要求dp[i][j]就必須考慮到s[i-1]與p[j-1]
              2.1 當p[j-1]不是'*'時
                  2.1.1 若s[i-1]==p[j-1]時,即p[j-1]為'a'-'z'且與s[i-1]相等,看dp[i-1][j-1]
                  2.1.2 p[j-1] == '.'時,直接將'.'變成s[i-1],看dp[i-1][j-1]
                  注意:這里的'.'是匹配一個字符,而不是一連串,如"a.b"->"axb"
              2.2 當p[j-1]是'*'時,主要看p[j-2]做判斷
                  2.2.1 p[j-2]為'a'-'z'并且p[j-2]==s[i-1],那么此時s繼續(xù)往前看,p暫時不動
                      即:看dp[i-1][j]
                  2.2.2 p[j-2]為'.',那么".*"可以變?yōu)?....."可以匹配s[i-1]前面的任何字符(萬能串)
                      因此,直接看dp[i-1][j](或者直接返回true)
                  2.2.3 剩下的就是p[j-2]為'a'-'z'且p[j-2]!=s[i-1],那么此時p的"x*"作廢,看dp[i][j-2]
              這里:2.1.1與2.2.2可以看成一種情形:即s與p均前移一位
                  2.2.1與2.2.2可以看成一種情形:即p不動s前移一位
          3.初始化:
              3.1 空的s
                  3.1.1 空的p,空的s可以匹配空的p,因此dp[0][0]=true
                  3.1.2 非空的p,空的s可能可以匹配非空的p,例如"a*",因此需要經(jīng)過轉移計算
              3.2 空的p
                  3.2.1 空的s,同3.1.1
                  3.2.2 非空的s,空的p不可能匹配非空的s,因此dp[i][0]=false,i∈[1,m]
              3.3 非空的s與非空的p:需要經(jīng)過轉移計算
              其中:3.1.1與3.2.2可以合并為dp[i][0]=i==0
          4.遍歷順序:顯然是正序遍歷
          5.返回形式:返回dp[m][n]就是考慮s[0,m-1]與p[0,n-1]是否能匹配上
          */
          int m = s.length(), n = p.length();
          boolean[][] dp = new boolean[m + 1][n + 1];
          // 初始化dp[i][0]
          // for(int i = 0; i <= m; i++) {
          //     dp[i][0] = i == 0;
          // }
          dp[0][0] = true;
          // i從0開始
          for(int i = 0; i <= m; i++) {
              // 注意j從1開始
              for(int j = 1; j <= n; j++) {
                  if(p.charAt(j - 1) != '*') {
                      // 1.當p[j-1]不是'*'時(注意j已經(jīng)從1開始了)
                      // 這里要注意運算優(yōu)先級問題(加括號)
                      if(i >= 1 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                          // s與p均前移一位
                          dp[i][j] = dp[i - 1][j - 1];
                      }
                  } else {
                      // 2.當p[j-1]是'*'時,主要看p[j-2]做判斷
                      if(j >= 2 && i >= 1 && 
                      (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.')) {
                          // 看"x*":p不動s前移一位
                          dp[i][j] = dp[i - 1][j];
                      }
                      // 不看"x*":
                      // 剩下的為p[j-2]為'a'-'z'且p[j-2]!=s[i-1],那么此時p的"x*"作廢,看dp[i][j-2]
                      if(j >= 2) {
                          dp[i][j] |= dp[i][j - 2];
                      }
                      // 這里的|=表示只要滿足了其中一個條件就可以使得dp[i][j]==true
                      // 通俗一點的解釋就是:當p[j-1]=='*'時,
                      // 若p[j-2]==s[i-1]||p[j-2]=='.',則dp[i][j]可以繼承dp[i-1][j]:轉移路徑1
                      // 若p[j-2]!=s[i-1],則dp[i][j]可以繼承dp[i][j-2]:轉移路徑2
                      // 滿足任意一條轉移路徑就可以使得dp[i][j]=true
                  }        
              }
          }
          // 所求即為考慮s[0,m-1]與p[0,n-1]是否能匹配上
          return dp[m][n];
      }
  }
  

  詳情參考官方代碼

  復雜度分析：

  • 時間復雜度：$O(n?m)$
  • 空間復雜度：$O(n?m)$

  其中 $n$ 為數(shù)組中元素的個數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-462752.html

到了這里，關于【LeetCode熱題100】打卡第6天：正則表達式匹配的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！