題目要求

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

實例圖

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

題目分析

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

遞歸條件判別表

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

代碼實現(xiàn)

該代碼參考自LeetCode討論區(qū)。
??上圖中的第2、3、4個條件因為判斷情況相同，合并為一個判斷。

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é)

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