題目要求

Implement regular expression matching with support for '.' and '*'

實(shí)例圖

題目翻譯：實(shí)現(xiàn)正值表達(dá)式中兩個(gè)功能：（英文）句號(hào)和星號(hào)，規(guī)則如實(shí)例圖。句號(hào)匹配任意一個(gè)字符；星號(hào)表示它之前的字符可以出現(xiàn)0次或任意多次。

題目分析

該問(wèn)題每一步匹配都會(huì)出現(xiàn)多種條件判別情況，情況為有限多種，且條件判別一定會(huì)終止，可以用遞歸來(lái)實(shí)現(xiàn)。
??定義一個(gè)isMatch遞歸函數(shù)進(jìn)行匹配，此時(shí)問(wèn)題的難點(diǎn)在于，當(dāng)前這一步有多種情況，因?yàn)槌霈F(xiàn)兩個(gè)變量：s 和 p。為了邏輯清晰，先對(duì) p 做條件判斷，在此基礎(chǔ)上，對(duì) s 做條件判斷。
??列出如下遞歸條件判別表：

遞歸條件判別表

對(duì)于第4個(gè)條件：當(dāng)p的第二個(gè)字符不是星號(hào)時(shí)，如果S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)==‘ . ’)，則進(jìn)入下一層遞歸繼續(xù)比較分別截取首元素的s和p；否則，返回false。
??對(duì)于第5個(gè)條件：當(dāng)p的第二個(gè)字符是星號(hào)時(shí)，如果S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)==‘ . ’)，有兩種分支需要分別判斷：
1、某字符+星號(hào)不要匹配s的首字符：（因?yàn)樾翘?hào)之前的字符可出現(xiàn)可不出現(xiàn)，該情況不配是考慮到后面有必須匹配的。假設(shè)當(dāng)前匹配并截去s的首字符，會(huì)導(dǎo)致后續(xù)匹配錯(cuò)誤。） 截去p的前兩個(gè)元素（某字符+星號(hào)）并進(jìn)入下一層遞歸，假如返回true，則當(dāng)前遞歸返回true；假如返回false，進(jìn)入分支2。
2、某字符+星號(hào)要匹配s的首字符：截去s首字符并繼續(xù)條件5的判斷。
??對(duì)于第6個(gè)條件：當(dāng)p的第二個(gè)字符是星號(hào)時(shí)，非【S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)==‘ . ’)】，截去p的前兩個(gè)元素（某字符+星號(hào)）并進(jìn)入下一層遞歸。

代碼實(shí)現(xiàn)

該代碼參考自LeetCode討論區(qū)。
??上圖中的第2、3、4個(gè)條件因?yàn)榕袛嗲闆r相同，合并為一個(gè)判斷。

package com.linsiyue;
public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        
        if (p.length() == 1 || p.charAt(1) != '*') {
            if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))) {
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            s = s.substring(1);
        }
        
        return isMatch(s, p.substring(2));
    }
}

心得總結(jié)

對(duì)于復(fù)雜的遞歸條件判斷問(wèn)題，可先對(duì)一個(gè)變量做判斷，在此基礎(chǔ)上對(duì)下一個(gè)變量做判斷，這樣才能思路清晰；為了利于所有條件分解以及相同判斷的條件合并，可以采用遞歸條件判別表輔助分析。