题解 | #正则表达式匹配#

对于字符串 s 来说，没有特殊字符，当前问题中字符只会是字母，但是对于 p 来说，我们需要考虑两个特殊符号，还有字母，这里列举所有的可能，如果说当前的子问题是 s[i,…n] 和 p[j…m]:

• s[i] == p[j]，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]

• p[j] == ‘.’，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]

• p[j+1] == ‘*’，s[i] != p[j]，子问题成立与否取决于子问题 s[i,…n] 和 p[j+2,…m]

• p[j+1] == ‘*’，s[i] == p[j]，子问题成立与否取决于子问题 s[i+1,…n] 和 p[j,…m]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        
    if (str.equals(pattern)) {
        return true;
    }

    boolean isFirstMatch = false;
    if (!str.isEmpty() && !pattern.isEmpty() && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.')) {
        isFirstMatch = true;
    }

    if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
        // 看 s[i,...n] 和 p[j+2,...m] 或者是 s[i+1,...n] 和 p[j,...m]
        return match(str, pattern.substring(2))
                 || (isFirstMatch && match(str.substring(1), pattern));
    }

    // 看 s[i+1,...n] 和 p[j+1,...m]
    return isFirstMatch && match(str.substring(1), pattern.substring(1));
   }
    
}