LeetCode 正则表达式中"."与&qu

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

LeetCode题目：10. Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a") → true
isMatch("aa", ".") → true
isMatch("ab", ".") → true
isMatch("aab", "cab") → true

class Solution {
    
    // 迭代算法
    public boolean isMatch(String text, String pattern) {
        
        // match[i][j] 表示 text[i + 1, i + 2....] 和 pattern[j + 1, j + 2....] 是否match
        boolean[][] match = new boolean[text.length() + 1][pattern.length() + 1];
        
        match[text.length()][pattern.length()] = true;
        
        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean firstMatch = (i < text.length() && 
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                
                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                    match[i][j] = match[i][j + 2] || first_match && match[i + 1][j];
                } else {
                    match[i][j] = first_match && match[i + 1][j + 1];
                }
            }
        }
        return match[0][0];
    }
    
    // 递归算法
    public boolean isMatchRecursive(String text, String pattern) {
        // 都为空
        if (text.isEmpty() && pattern.isEmpty()) return true;
        
        // pattern为空，text不为空
        if (pattern.isEmpty()) return false;
        
        // 允许存在text为空，pattern不为空的情况，例如 text = "", pattern = "a*"
        
        // 第一个字符是否匹配
        boolean firstMatch = (!text.isEmpty() && 
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        
        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            // case1: 由于 * 的出现，之前的那个字符出现0次，比较 text 与 pattern.substring(2)
            boolean case1 = isMatch(text, pattern.substring(2));
            
            // case2: 由于 * 的出现，之前的那个字符出现多次，比较 text.substring(1) 与 pattern
            boolean case2 = firstMatch && isMatch(text.substring(1), pattern);
            
            return case1 || case2;
        } else {
            return firstMatch && isMatch(text.substring(1), pattern.substring(1));
        }
}

详细解读，包括递归和非递归算法：https://leetcode.com/articles/regular-expression-matching/

LeetCode题目：44. Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "") → true
isMatch("aa", "a") → true
isMatch("ab", "?") → true
isMatch("aab", "cab") → false

class Solution {
    public boolean isMatch(String s, String p) {
        // Bottom-Up Variation 自底向上的DP
        boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
        
        match[s.length()][p.length()] = true;
        
        for(int i = p.length() - 1; i >= 0; i--){
            if(p.charAt(i) == '*') {
                match[s.length()][i] = true;
            }
            else {
                break;
            }
        }
        
        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = p.length() - 1; j >= 0; j--) {
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
                    match[i][j] = match[i + 1][j + 1];
                }
                else if(p.charAt(j) == '*') {
                    match[i][j] = match[i + 1][j] || match[i][j + 1];
                }
                else {
                    match[i][j] = false;
                }
            }
        }
        
        return match[0][0];
    }
}