LeetCode OJ--Regular Expression Matching

http://oj.leetcode.com/problems/regular-expression-matching/

问题给想复杂了，只有p中可以含有. *，s中的字符都是确定的。想了好久，最终还是参考了网上的答案。等我再想想。

#include <iostream>

#include <map>

#include <string>

using namespace std;

class Solution {

public:

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

    {

        if (s == NULL || p == NULL) return false;

        if (*p == '\0') return *s == '\0';

        if (*(p + ) == '*')

        {

            while ((*s != '\0' && *p == '.') || *s == *p)

            {

                if (isMatch(s, p + )) return true; //aab a*cd

                ++s;

            }

            return isMatch(s, p + ); //aab c*ab 的情况

        }

        else if ((*s != '\0' && *p == '.') || *s == *p)

        {

            return isMatch(s + , p + );

        }

        return false;

    }

};

int main()

{

    Solution myS;

    char *s = "aab";

    char *p = "a*cd";

    myS.isMatch(s,p);

    return ;

}

于是，又试图用自己的解法，来做这道题。

class Solution {

public:

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

    {

        if (s == NULL || p == NULL) return false;

        int j = ,i = ;

        char flagchar = '\0';

        while(s[i]!='\0'&&p[j]!='\0')

        {

            if(s[i] == p[j] )

            {

                flagchar = s[i];

                i++;

                j++;

            }

            else if(p[j] == '.')

            {

                i++;

                j++;

                flagchar = '\0';

            }

            else if(s[i]!= p[j] && p[j]!= '*' && p[j] != '\0' && p[j+]!='\0' && p[j+] == '*')

            {

                flagchar = p[j];

                j+= ;

            }

            else if(p[j]=='*')

            {

                if(flagchar == '\0')

                    flagchar = s[i];

                while(p[j+]!='\0'&&p[j+]==flagchar)

                    j++;

                j++;

                while(s[i]!='\0'&&s[i]==flagchar)

                    i++;

            }

            else

                break;

        }

        if(s[i]=='\0'&&p[j]=='\0')

            return true;

        return false;

    }

};

但是在"aaa", "ab*a*c*a"里，挂掉了。发现，当该边的只是规模的时候，确实递归非常好用。在这个地方，确实得递归。

在多种情况匹配不确定的时候，这个尝试

while ((*s != '\0' && *p == '.') || *s == *p)

{

    if (isMatch(s, p + 2)) return true; //aab a*cd

         ++s;
}

  return isMatch(s, p + 2); //aab c*ab 的情况
这里，大赞啊！
又长智商了。

巴特西

LeetCode OJ--Regular Expression Matching

最新文章

热门文章