【leetcode】10. Regular Expression Matching

最新推荐文章于 2024-02-23 10:40:54 发布

artemisrj

最新推荐文章于 2024-02-23 10:40:54 发布

阅读量391

点赞数

分类专栏： leetcode 文章标签： leetcode

本文链接：https://blog.csdn.net/artemisrj/article/details/51812312

版权

leetcode 专栏收录该内容

48 篇文章

订阅专栏

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

思路是用分治算法，然后设置每次符合要求的时候return,主要分为三种情况，一种情况是用来判断终结的，第二种主要是用来判断*的，它也分为两种，还有一种情况就是字母相同的时候。

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    if(s===p){
        return true;
    }else{
        if(p===""){
            return false;
        }
        if(s===""){
            if(p[1]==="*"){  //p为空 p.slice(2)也为空
                if(isMatch(s,p.slice(2))){
                    return true;
                }
            }else{
                return false;
            }
        }else if(p[1]!=="*"){
            if(s[0]===p[0]||p[0]==="."){
                if(isMatch(s.slice(1),p.slice(1))){
                    return true;
                }
            }else{
                return false;
            }
        }else{
            if((s[0]===p[0]||p[0]===".")&&isMatch(s.slice(1),p)){
                return true;
            }
            if(isMatch(s,p.slice(2))){
                return true;
            }

        }
        return false;
    }
};