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

2021/11/27 17:12:58

本文主要是介绍Java之自定义正则表达式匹配算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

前言

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

一、题目

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符,而’/*'表示它前面的字符可以出现任意次(含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 原题



这篇关于Java之自定义正则表达式匹配算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程