Regular Expression Matching正则表达式匹配

前端之家收集整理的这篇文章主要介绍了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","c*a*b") → true

.表示内容,匹配任意字符。

*表示数字,匹配前面的0个或者任意多个字符。

核心思路是:

每次我们看pattern的时候,看2个。

可以分为2种情况。

1. a* 这种,第二个字符是*

这个时候,我们看第一个字符,如果s中的当前第一个字符和p的当前第一个字符不相等,那么我们只能表示0个匹配。

比如s = 'b' p = 'a*b',pattern中的'a*'匹配0个a,相当于继续看后面的s = 'b',p = 'b'。

如果当前字符相等,表示匹配是合法的。

这时候,我们可以选择匹配0个,也可以选择匹配1个。

如果s后面的字符依旧相等,我们可以继续匹配2个...

然后看后面的匹配(利用递归)

2. aa 这种,第二字符不是*

第2种是好办的,如果pattern不是'.',且2个字符不相等的话,直接返回false了。

如果相当,继续看后面的匹配(利用递归)

递归的终止条件:

1. s 和p都匹配到了最末尾。说明匹配成功

2. p匹配到了最末尾,s没有,说明匹配失败

3. s匹配到了最末尾,p没有,p后面跟着a*这类的,我们可以匹配0个,还可以继续匹配,否则就是匹配失败了。

运行时间:


代码

public class RegularExpressionMatching {
    public boolean isMatch(String s,String p) {
        return doMatch(s,p,0);
    }

    private boolean doMatch(String s,int sIndex,String p,int pIndex) {
        if (sIndex == s.length() && pIndex == p.length()) {
            return true;
        }
        if (pIndex == p.length()) {
            return false;
        }
        if (sIndex == s.length()) {
            if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
                return doMatch(s,sIndex,pIndex + 2);
            }
            else {
                return false;
            }
        }
        if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
            if (p.charAt(pIndex) != '.' && s.charAt(sIndex) != p.charAt(pIndex)) {
                return doMatch(s,pIndex + 2);
            }
            if (doMatch(s,pIndex + 2)) {
                return true;
            }
            for (int i = sIndex; i < s.length(); i++) {
                boolean result = false;
                if (p.charAt(pIndex) == '.' || s.charAt(i) == p.charAt(pIndex)) {
                    result = doMatch(s,i + 1,pIndex + 2);
                    if (result) {
                        return true;
                    }
                } else {
                    return false;
                }
            }
        } else {
            if (p.charAt(pIndex) == '.' || p.charAt(pIndex) == s.charAt(sIndex)) {
                return doMatch(s,sIndex + 1,pIndex + 1);
            } else {
                return false;
            }
        }
        return false;
    }
}
原文链接:https://www.f2er.com/regex/359125.html

猜你在找的正则表达式相关文章