JZ19-题解 | #正则表达式匹配#

正则表达式匹配

http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4

题目描述


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

算法思路:引自Maokt 每次从字符串里取出一个字符与模式中的字符匹配,如果模式中的字符是‘.’,它可以匹配字符串中的任意字符,如果不是,那么如果它与字符串中的字符相等则匹配。当字符串的字符和模式的字符匹配时,接着匹配后面的字符。
下面,考虑模式中的第二个字符是不是‘* ’。如果不是,则可以分为两种情况:

1、如果字符串中的第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的字符串和模式;
2、如果字符串中的第一个字符和模式中的第一个字符不匹配,则直接返回false。 当模式中的第二个字符是‘* ’时,又可以分为两种情况方式:
1、如果pattern中的第一个字符和str中的第一个字符不匹配,则将pattern后移两个字符,相当于忽略‘’和它前面的字符,因为‘’可以匹配字符串中的0个字符;
2、如果pattern中的第一个字符和str中的第一个字符匹配,则str后移一个字符,而在模式上又有两种选择:
2.1、pattern后移两个字符(例如字符串"ab"和模式"a* ab"匹配到str[0]和pattern[0]时,pattern后移两个字符,字符串后移一个字符)
2.2、pattern保持不变(例如字符串"aabbba"和模式"aab* a"匹配到str[2]和pattern[2]时,pattern保持不变,字符串后移一个字符)


代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool myMatch(string &s, string &p, int i, int j){
        if(i<0&&j<0)
            return true;
        if(j<0)
            return false;
        //匹配一般字符
        if(i>=0&&s[i]==p[j])
            return myMatch(s, p, i-1, j-1);
        //匹配.
        if(i>=0&&p[j]=='.')
            return myMatch(s, p, i-1, j-1);
        //匹配*
        if(p[j]=='*'){
            //匹配0个字符
            if(myMatch(s, p, i, j-2))
                return true;
            //匹配一个字符后递归调用
            if(i>=0&&(p[j-1]=='.'||s[i]==p[j-1]))
                if(myMatch(s, p, i-1, j))
                    return true;
        }
                return false;
    }
    bool match(string str, string pattern) {
        // write code here
        return myMatch(str, pattern, str.size()-1, 											pattern.size()-1);
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:06
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-25 13:59
点赞 评论 收藏
分享
06-07 00:00
已编辑
腾讯_后端开发
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务