Leetcode — 10. Regular Expression Matching (中文)

問題連結: https://leetcode.com/problems/regular-expression-matching/

回傳給予的字串 (s) 是否可成功對應 使用了 '.' 和'*' 的正規表達式regular expression 的模板字串 (p):

• '.' 可對應任何字元
• '*' 對應0或多個在這之前的某字元

且套用需整個字串可以套用在整個模板字串, 不可只有部分字串套用成功

範例 1
Input: s = "aa", p = "a*"
Output: true
解釋: p字串中的'*'代表是前一個字元'a', 因此我們若重複a兩次, 就可以得到字串s
--------------------------------------------------------------------範例 2
Input: s = "ab", p = ".*"
Output: true
範例: 因為".*"代表"0或多個(*)的任一字元(.)"

想法:

這題真的超難, 我也是花了很久才搞懂可以怎麼做, 一開始的想法是一個一個檢查, 但又要考慮星號*可以代表0或多個, 代表就算現在我們這樣比對不成, 也不能直接回false, 因為可能這時候我們可以忽略這字元而接下去繼續比, 總之要考慮的情況太多, 需要考慮各可能情況, 發現真的不可能match的時候才回傳最終結果

這個問題就難在我們要特別處理*的可能性, 不如我們把我們需要考量的東西都寫下來, 看可不可以拆解題目讓他變成更簡單一點

假設s真的能成功套用整個pattern字串p, 代表若我們在特定位置切開s跟p, 應該也可以套用, 不然不可能整個字串能成功對應, 因此我們可以這樣想 — 決定s可否套用p的模板也是從他們各別的子字串看出來的, 若s的子字串全部都無法套用p子字串的模板的話, 我們就知道s不可能能套用p模板了

因此也可以解釋成, s的某子字串 能否套用 p的某子字串模板 的條件, 決定於在這之前的子字串可否套用, 如果沒有的話, 那現在組成的子字串們就不可能可以套用目前模板

這種 需要依靠前面辛苦的結果, 來判斷現在位置的結果的邏輯, 就可以發現其實這題正是可以用動態規劃dp來幫忙, 因為我們切割s和p的子字串的時候, 他們長度不一定相同, 比如(aaa和a*) 或 (a 跟 a*) 這兩組皆是可套用模板的字串, 但s長度可能比p長也可能比p短, 因此我們為了記錄是s字串的哪部分套用在p中哪部分的模板字串, 我們把我們組成過的子字串比對結果們存放在二維陣列, 讓dp[i][j]代表 s字串中前i個字母 可否套用p字串中前j個字元這個模板

因此, 假設s = ”aaabcde”, p = “a*bvc”, 而dp[2][3]則代表s中的”aa” 是否能套用p中的”a*b”的模板

那我們先來想我們要如何得知dp[i][j]的值:

⚠️以下為了方便解釋, 我們將s字串中前i個字母簡寫為s[0,i-1], 代表是從index 0 到 index i-1之間的子字串; p字串中前j個字母簡寫為p[0,j-1], 代表是從index 0 到 index j-1之間的子字串 (1≤ i ≤ s的總長度, 1≤ j≤ p的總長度)

不可避免的, 我們第一件做的事情是檢查p在第j個字元curP, 以下將curP 可能的字元分成下列三種情況 (將假設s在第i個字母為curS)

1. curP若為字母, 那情況很單純, 我們只要比較curS和curP是否相同, 若兩字元不相同, 那我們已知s[0, i-1]不可套用p[0, j-1]的模板字串; 若兩字元相同, 則我們需要看 在curS之前的子字串是否能套用 在curP之前的子字串模板(也就是 s[0, i-2] 和 p[0, j-2]), 而我們因為都把結果存在二維陣列dp中了, 因此dp[i][j]的答案將依dp[i-1][j-1]來決定

👷假設: s[0, i-1] = "ac", p[0, j-1] = "oac" 雖然curS和curP皆為相同字元'c', 但因為s[0,i-2] ("a") 和 p[0, j-2] ("oa")兩者不匹配, 因此dp[i][j]為false

2. curP若為一個點 ‘.’ 那情況也很單純, 因為”點”代表任一字母皆可與其搭配, 代表只要curS有東西, 我們就把兩字元認為相同字元, 而同上面第一點, 我們也要檢查在curS之前的子字串是否能套用curP之前的子字串模板 i.e., 參考dp[i-1][j-1]才能決定dp[i][j]的值

3. curP若為星號, 則情況將複雜許多, 因為星號一定跟隨著某字母或點, 代表我們也需要把curP的前一個字元prevP考慮進來!
那我們先來比較curS和prevP兩個字元, 若他們”相同” (curS字元同prevP 或prevP是一個點), 則我們需要往前參考, 但這次我們要參考dp[i-1][j]來決定dp[i][j]的值, (若我們參考dp[i-1][j-1], 代表我們只允許s[0, i-2]裡面最後只能有一個同prevP的字母, 並不符合星號允許多個的狀態)
而若s[0, i-2]能套用現在的p[0, j-1]模板字串, 那代表我們不管加1個或多個prevP 到 s[0, i-2]的最後面, 都應仍然能套用現在這個模板 (i.e. p[0, j-1])

👷 假設: s[0, i-1] = “accc”, p[0, j-1] = “ac*”, curS和prevP皆為相同字元’c’, 因此我們想要知道 “acc” 是否能套用模板 “ac*” 
若可以, 則我們可以放心把curS加上去, 因為知道我們這樣累加也不會影響原本成功套用模板的狀態, 代表我們可以放心的加無數個c在現在子字串s'的後面
(但若我們檢查成dp[i-1][j-1] (也就是s'的"acc"可否套用p'的"ac"), 我們反而會得到錯誤答案, 會認為為s'的c太多餘,而回傳false)

但其實不要忘記星號的規則 — 他可以代表0至多個字元, 現在我們只考慮到當curP和prevP相同的情況, 但我們沒考慮到我們允許在s中沒有prevP的可能性!

因此, 判斷 dp[i][j] 可能有兩種機會為true —
1. 當curS和prevP可被視為同字母, 且s[0, i-2]可以套用 p[0, j-1]的模板, 也就是當dp[i-1][j]為true (當我們考慮prevP有一個或多個)

2. 當s[0, i-1]可以套用p[0, j-3]的模板, 也就是當dp[i][j-2]為true (當我們直接忽略prevP和緊跟著他的星號curP, 代表prevP是0個)

👷 假設: s[0, i-1] = “ka”, p[0, j-1] = “ka*c*”
雖然curS和prevP為不同字元, 但別急著直接設定dp[i][j]為false! 
我們來看有沒有可能我們直接忽略c*, 因此我們要檢查s'的"ka"是否可以套用p'的"ka*"模板, 答案是可以, 代表我們可以放心的把c*這個字串加到p'的後面且不影響現在成功套用狀態

程式邏輯:

我們每輪loop都會先決定這次我們要找s的子字串s’可以匹配的pattern, 切好字串s拿到s’後, 再開始依序切割字串p 來看當我們切字串p的時候那些子字串p’可以被現在的子字串s’ 成功套用

其實程式碼的邏輯都在上面分析過了, 但我們二維陣列dp的初始狀態如何設定很重要:

1. 一開始所有值都為false, 因為還沒開始做任何檢查
2. 當s的長度跟p的長度為0的時候, 空字串可套用另一個空字串模板, 因此dp[0][0]為true
3. 當只有s的長度為0的時候, 空字串只有在一種情況下才成功套用p字串模板 — 模板只要有字母或一點(.), 後面一定必須跟隨星號, 比如說 “a*b*.*c*” 因此我們這邊有需要特別跑一個loop來檢查dp[0][j]的狀態
4. 當只有p的長度為0的時候, 只要s的長度沒有跟著為0, 皆視為false

以下為1ms程式碼, 贏過100% —

public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        //dp[i][j] means if s.substr(0,i) and p.substr(0,j) matches
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int j=2;j<=n;j++)
            dp[0][j] = p.charAt(j-1)=='*' && dp[0][j-2];
        for(int i=1;i<=m;i++)
        {
            char curS = s.charAt(i-1);
            for(int j=1;j<=n;j++)
            {
                char curP = p.charAt(j-1);
                if(curS==curP || curP =='.')
                    dp[i][j] = dp[i-1][j-1];
                else if(curP=='*')
                {
                    if(dp[i][j-2])//totally ignore prevP and curP
                        dp[i][j] = true;
                    else
                    {
                        //need to include prevP
                        char prevP = p.charAt(j-2);
                        if(prevP==curS || prevP =='.')
                            dp[i][j] = dp[i-1][j];
                    }
                }
            }
        }
        
        return dp[m][n];
    }