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之自定义正则表达式匹配算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript编程
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript
- 2024-12-26JS编程入门指南:从零开始学习JavaScript
- 2024-12-25Java编程面试题详解与解答
- 2024-12-25TS基础知识详解:初学者必看教程
- 2024-12-252024面试题解析与攻略:从零开始的面试准备指南
- 2024-12-25数据结构与算法学习:新手入门教程
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南