【JAVA、C++】LeetCode 010 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


这道题初学者或多或少都参考了网上的答案，主要难点有以下
一、要理解正则表达式中.和*的含义，“.”代表任意字符，但是“a*”代表“”，“a”，“aa”，“aaa”……这一点比较容易让人犯迷糊
二、必须完全比配，即isMatch("aa","aaa") → false
三、第一个参数String s 是不含有“.”和“*”，因此不要把程序复杂化
Java实现如下：

static public boolean isMatch(String s, String p) {

        // 如果从s长度入手，s.length() == 0时（"","a*")、("","a*b*")都会返回true

        if (p.length() == 0)

            return s.length() == 0;

        else if (p.length() == 1)

            return s.length() == 1&& (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0));

        if (p.charAt(1) != '*') {

            if (s.length() == 0|| (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))

                return false;

            return isMatch(s.substring(1), p.substring(1));

        }

        else if (isMatch(s, p.substring(2)))

                return true;

        else {

                int i = 0;

                while (i < s.length()&& (p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))) {

                    if (isMatch(s.substring(i + 1), p.substring(2)))

                        return true;

                    i++;

                }

            }

            return false;

    }

C++面向对象：

 class Solution {

 public:

     bool isMatch(string s, string p) {

         if (p.length() == )

             return s.length() == ;

         else if (p.length() == )

             return s.length() ==  && (p[] == '.' || s[] == p[]);

         if (p[] != '*') {

             if (s.length() ==  || (p[] != '.' && s[] != p[]))

                 return false;

             return isMatch(s.substr(), p.substr());

         }

         else if (isMatch(s, p.substr()))

             return true;

         else {

             int i = ;

             while (i < s.length() && (p[] == '.' || p[] == s[i])) {

                 if (isMatch(s.substr(i + ), p.substr()))

                     return true;

                 i++;

             }

         }

         return false;

     }

 };

C++ 面向过程（效率高）：

 class Solution {

 public:

 bool isMatch(const char *s, const char *p) {

         if (!p[])

             return !s[];

         if (!p[] || p[] != '*')

             return s[] && (p[] == '.' || s[] == p[])&& isMatch(++s, ++p);

         while (s[] && (p[] == '.' || s[] == p[]))

             if (isMatch(s++, p + ))

                 return true;

         return isMatch(s, p + );

     }

     bool isMatch(string s, string p) {

         return isMatch(s.data(), p.data());

     }

 };

巴特西

【JAVA、C++】LeetCode 010 Regular Expression Matching

最新文章

热门文章