乘風(fēng)破浪：LeetCode真題_010_Regular Expression Matching

一、前言

? ? 關(guān)于正則表達(dá)式我們使用得非常多，但是如果讓我們自己寫一個(gè)，卻是有非常大的困難的，我們可能想到狀態(tài)機(jī)，確定，非確定狀態(tài)機(jī)確實(shí)是一種解決方法，不過需要消耗很大的時(shí)間去推理和計(jì)算，對于正則表達(dá)式的縮小版，我們往往可以通過遞歸，遞推，動態(tài)規(guī)劃等方法來解決。

二、Regular Expression Matching

2.1 問題理解

2.2 問題分析和解決

??? 遇到這樣的問題，我們想到了遞歸，對于.是很好處理和匹配的，但是如果和*結(jié)合起來就變化無窮了，正是因?yàn)?我們才要遞歸。

??? 讓我們看看官方的答案：

class Solution {public boolean isMatch(String text, String pattern) {if (pattern.isEmpty()) return text.isEmpty();boolean first_match = (!text.isEmpty() &&(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));if (pattern.length() >= 2 && pattern.charAt(1) == '*'){return (isMatch(text, pattern.substring(2)) ||(first_match && isMatch(text.substring(1), pattern)));} else {return first_match && isMatch(text.substring(1), pattern.substring(1));}} }

??? 如果模式串和源串第一個(gè)字符能夠正常匹配，并且不為空，模式串的第二個(gè)字符不為'*'，那么我們可以繼續(xù)遞歸匹配下面的東西：

1 return first_match && isMatch(text.substring(1), pattern.substring(1));

??? 如果模式串的長度大于1，并且第二個(gè)字符是*,那么我們就有可能匹配到源串的很多的字符，也就相當(dāng)于將源串已經(jīng)匹配的去掉，拿剩下的和整個(gè)模式串繼續(xù)比較，此時(shí)*發(fā)揮了作用，或者比較源串與去掉了*的模式串，因?yàn)?沒有能夠發(fā)揮作用。于是就得到了：

1 if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ 2 return (isMatch(text, pattern.substring(2)) || 3 (first_match && isMatch(text.substring(1), pattern))); 4 }

???? 除此之外我們還可以使用動態(tài)規(guī)劃算法：

class Solution {public boolean isMatch(String text, String pattern) {boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];dp[text.length()][pattern.length()] = true;for (int i = text.length(); i >= 0; i--){for (int j = pattern.length() - 1; j >= 0; j--){boolean first_match = (i < text.length() &&(pattern.charAt(j) == text.charAt(i) ||pattern.charAt(j) == '.'));if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];} else {dp[i][j] = first_match && dp[i+1][j+1];}}}return dp[0][0];} }

???? 首先我們定義dp[i][j]代表源串T[i:]和模式串P[j:]是匹配的，其中i,j為源串和模式串的下標(biāo)，于是我們只要求得dp[0][0]的值就可以了。我們已知的條件是：

dp[text.length()][pattern.length()] = true;

???? 于是我們從后往前倒求最終的dp[0][0]，通過如下的判斷，看看是哪一種情況，然后根據(jù)相應(yīng)的情況采取不同的遞推策略，最終得到結(jié)果：

1 boolean first_match = (i < text.length() && 2 (pattern.charAt(j) == text.charAt(i) || 3 pattern.charAt(j) == '.')); 4 if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){ 5 dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j]; 6 } else { 7 dp[i][j] = first_match && dp[i+1][j+1]; 8 }

?????? 同樣的我們算法也是使用了遞歸和動態(tài)規(guī)劃：

??? 在動態(tài)規(guī)劃方面我們使用match[i]來表示對于源串從i到最后（T[i:]）都是能夠匹配的，于是之用求match[0]即可。

import java.util.Arrays;public class Solution {/*** Implement regular expression matching with support for '.' and '*'.* '.' Matches any single character.* '*' Matches zero or more of the preceding element.** 題目大意：* 實(shí)現(xiàn)一個(gè)正則表達(dá)式匹配算法，.匹配任意一個(gè)字符，*匹配0個(gè)或者多個(gè)前導(dǎo)字符*/public boolean isMatch(String s, String p) {boolean[] match = new boolean[s.length() + 1]; Arrays.fill(match, false);match[s.length()] = true;//剛開始滿足需要for (int i = p.length() - 1; i >= 0; i--) {if (p.charAt(i) == '*') {for (int j = s.length() - 1; j >= 0; j--) {
　　　　　　　　　　//原來就是false只有能夠?yàn)檎?#xff0c;才為真。match[j] = match[j] || match[j + 1]&& (p.charAt(i - 1) == '.' || s.charAt(j) == p.charAt(i - 1));}i--;} else {for (int j = 0; j < s.length(); j++) {
//從前往后，只有到了已經(jīng)有true的時(shí)候才能生效。如果從后往前反而有問題。 match[j] = match[j + 1]&& (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));}//將最后的置為假，本來就應(yīng)該不真，便于以后的判斷match[s.length()] = false;}}return match[0];}// 下面的代碼用時(shí)比較長public boolean isMatch2(String s, String p) {// 輸入都為nullif (s == null && p == null) {return true;}// 有一個(gè)為nullelse if (s == null || p == null) {return false;}return isMatch(s, 0, p, 0);}/*** 正則表達(dá)式匹配** @param s 匹配串* @param sIdx 當(dāng)前匹配的位置* @param p 模式串* @param pIdx 模式串的匹配位置* @return 匹配結(jié)果*/public boolean isMatch(String s, int sIdx, String p, int pIdx) {// 同時(shí)到各自的末尾if (s.length() == sIdx && p.length() == pIdx) {return true;}// 當(dāng)匹配串沒有到達(dá)末尾，模式串已經(jīng)到了末尾else if (s.length() != sIdx && p.length() == pIdx) {return false;}// 其它情況else {// 如果當(dāng)前匹配的下一個(gè)字符是*號if (pIdx < p.length() - 1 && p.charAt(pIdx + 1) == '*') {// 匹配串未結(jié)束并且當(dāng)前字符匹配（字符相等或者是.號）if (sIdx < s.length() && (s.charAt(sIdx) == p.charAt(pIdx) || p.charAt(pIdx) == '.')) {return isMatch(s, sIdx + 1, p, pIdx + 2) // 匹配串向前移動一個(gè)字符（只匹配一次）|| isMatch(s, sIdx + 1, p, pIdx) // 匹配串向前移動一個(gè)字符（下一次匹配同樣的（模式串不動））|| isMatch(s, sIdx, p, pIdx + 2); // 忽略匹配的模式串} else {// 忽略*return isMatch(s, sIdx, p, pIdx + 2);}}// 匹配一個(gè)字符if (sIdx < s.length() && (s.charAt(sIdx) == p.charAt(pIdx) || p.charAt(pIdx) == '.')) {return isMatch(s, sIdx + 1, p, pIdx + 1);}}return false;}}

?

??? 如下表所示，使用遞歸需要1163ms而使用動態(tài)規(guī)劃需要20ms，差別非常顯著。

三、總結(jié)

???? 對于一些比較困難的問題，我們需要從不同的角度考慮，解決問題的方法可以從遞歸，遞推，動態(tài)規(guī)劃等方面去考慮。

轉(zhuǎn)載于:https://www.cnblogs.com/zyrblog/p/10211390.html

總結(jié)

以上是生活随笔為你收集整理的乘风破浪：LeetCode真题_010_Regular Expression Matching的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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