peace唠叨

leetcode10-Regular Expression Matching之Java版本

我的leetcode之旅,该篇章主要完成使用Java实现算法。这是第10篇Regular Expression Matching

全部代码下载:Github链接:github链接,点击惊喜;写文章不易,欢迎大家采我的文章,以及给出有用的评论,当然大家也可以关注一下我的github;多谢;

1.题目简介:

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

2.我的思路:

我的思路:
1、由于存在号,我采用从尾部开始判断
2、使用递归减去两个字符串的尾部进行判断
3、对各种情况进行判断
4、分为二种大情况:
(1)p为’.’和s的最后一个字符与p的最后一个字符相等:isMatch(s.substring(0, n - 1), p.substring(0, m - 1));
(2)当p的最后一个字符为’
‘,又可以分为三种小情况,详见注释。

3.我的AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package com.rlovep.string;
/**
* Regular Expression Matching
* 我的思路:
* 1、由于存在*号,我采用从尾部开始判断
* 2、使用递归减去两个字符串的尾部进行判断
* 3、对各种情况进行判断
* 4、分为二种大情况:
* (1)p为'.'和s的最后一个字符与p的最后一个字符相等:isMatch(s.substring(0, n - 1), p.substring(0, m - 1));
* (2)当p的最后一个字符为'*',又可以分为三种小情况,详见注释。
* @author peace
*
*/

public class RegExpMatching {
public static boolean isMatch(String s, String p) {
// 字符串为空的判断
if (s == null && p == null)
return true;
if (s == null && p != null || s != null && p == null)
return false;
// 字符串不为空
int n = s.length(), m = p.length();
// p的长度为0时的判断
if (n == 0 && m == 0)
return true;
if (m == 0 && n != 0)
return false;
// m>0的判断
if (p.charAt(m - 1) == '.' && n > 0) {
return isMatch(s.substring(0, n - 1), p.substring(0, m - 1));// 匹配任意字符:将s去掉一个以及p去掉一个
} else if (p.charAt(m - 1) == '*') {// 对于*号的判断:精髓所在
if (m > 1) {// 当m>1则进行后面的判断
if (n > 0)// 当s字符串长度大于0则进行下面的判断
{
if (p.charAt(m - 2) == '.') {// 匹配任意字符:将s去掉一个以及p暂时不变
if (isMatch(s.substring(0, n - 1), p))
return true;// 如果返回true则直接返回,否则执行将p字符串去掉后面两个字符
} else if (p.charAt(m - 2) == '*') {
return false;// 连续两个的*直接退出
} else {
if (p.charAt(m - 2) == s.charAt(n - 1)) {
if (isMatch(s.substring(0, n - 1), p))
return true;
// 如果返回true则直接返回,否则执行将p字符串去掉后面两个字符
}
}
}
return isMatch(s, p.substring(0, m - 2));// 上面返回为FALSE和s长度为0时用的递归
}
} else {
if (n > 0) {
if (p.charAt(m - 1) == s.charAt(n - 1))
return isMatch(s.substring(0, n - 1), p.substring(0, m - 1));
// 此去为简单判断:当最后一个字符相等就执行减字符递归
}
}
return false;// 所有条件都不满足,则直接返回FALSE
}
public static void main(String[] args) {
System.out.println(isMatch("ab", ".*"));
}
}

好的本章介绍到这里 来自伊豚wpeace(blog.wpeace.cn)

Peace wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!