自定义正则表达式匹配算法

• 前言
• 一、题目
• 二、匹配算法
• 总结
• 参考文献

前言

自定义正则表达式规则，然后完成匹配算法的实现。

一、题目

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’/*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:
输入:
s = “ab”
p = “.*”
输出: true
解释: “.*” 表示可匹配零个或多个（’*’）任意字符（’.’）。

示例 4:
输入:
s = “aab”
p = “c*a*b”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:
输入:
s = “mississippi”
p = “mis*is*p*.”
输出: false

二、匹配算法

匹配的四种情况，把每种情况写好就OK了。
1）情况1：递归出口1，规则末尾，表达式未末尾，返回false。
2）情况2：递归出口2，规则末尾，表达式末尾，返回true。
3）情况3：递归出口3，规则未末尾，表达式末尾，此时的规则必须是带*号的。
4）情况4：正式递归1，规则未末尾，表达式未末尾，此时要根据是否有’*‘来for循环递归，或者无’*‘的简单递归。

package com.xhu.offer;

public class DFSForRE {
    private String s;
    private String p;

    public boolean isMatch(String s, String p) {
        if (".*".equals(p) || "".equals(s) && "".equals(p)) return true;
        this.s = s;
        this.p = p;

        /**
         * 思路：递归
         * 对应位置比较是否匹配，碰到s*这种需要for循环递归匹配，相当于dfs.
         */
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        //情况1：递归出口1，规则末尾，表达式未末尾，返回false
        if (j >= p.length() && i < s.length()) {
            return false;
        }
        //情况2：递归出口2，规则末尾，表达式末尾，返回true
        if (j >= p.length() && i >= s.length()) {
            return true;
        }
        //情况3：递归出口3，规则未末尾，表达式末尾，此时的规则必须是带*号的
        if (j < p.length() && i >= s.length()) {
            for (int n = j; n < p.length(); ) {
                if (n + 1 >= p.length() || p.charAt(n + 1) != '*')
                    return false;
                n+=2;
            }
            return true;
        }
        //情况4：正式递归，规则未末尾，表达式未末尾，此时要根据是否有’*‘来for循环递归，或者无’*‘的简单递归
        if (j + 1 < p.length()) {
            char ch = p.charAt(j + 1);
            if (ch != '*') {
                //点或字符的匹配
                char ch1 = s.charAt(i);
                char ch2 = p.charAt(j);
                if (ch2 == '.' || ch1 == ch2)
                    return dfs(i + 1, j + 1);
                else return false;
            } else {
                for (int n = -1; n < s.length() - i; n++) {
                    boolean flag = false;
                    //不用比
                    if (n == -1) {
                        flag = dfs(i, j + 2);
                    } else if (p.charAt(j) == '.' || s.charAt(i + n) == p.charAt(j)) {
                        //比较成功，同时进位
                        flag = dfs(i + n + 1, j + 2);
                    }else{
                        return false;
                    }
                    //如果成功就return，没必要循环了。
                    if (flag)
                        return true;
                }
                //带’*‘的能把所有都匹配了，即s中后面的字符都一样。但是字符规则还需字符去匹配，根据出口返回的是false。
                return false;
            }
        }
        //j+1越界，此时看i和j是否相等就可以了
        else if (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))
            return dfs(i + 1, j + 1);
        //j又是最后一位，i又不匹配，所以返回false
        else return false;
    }

}

总结

1）静下来认真刨析问题，完成问题拆解和分类。
2）递归和DFS思想很重要。

参考文献

[1] Leetcode 原题