LeetCode:Regular Expression Matching-白红宇

LeetCode:Regular Expression Matching

阅读量：5362 次

发布时间：2019-06-15

本文共 2014 字，大约阅读时间需要 6 分钟。

mplement 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

刚开始的时候，想的过于简单，就按照一般的比较方法，但是其实特殊性在于.*，想当然的认为前面匹配了，出现了.*就都是正确的。没有细致思考。

但是如果构造自动机感觉略复杂，而且不同的输入p，你想要构造自动机的话，这样过于复杂。所以利用递归就可以了。其实这个里面最特殊的就只有*这个字符，因为可以代表0个或者n个字符。sPoint和pPoint类似于指针。

分为2种情况：

1、pPoint + 1指向的是*时，pPoint 指向内容和sPoint指向内容相等，就可以测试*到底是代替多少个字符。当跳出循环就可以返回结果了。

2、就是剩下所有情况。pPoint和sPoint内容相同，或者pPoint为’.’就可以把sPoint和pPoint都向前移一格。

在提交后，发现还有输入待对比字符串为空的时候的这种特殊情况。

public class Solution {
    public boolean isMatch(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] s2 = p.toCharArray();
        int pStr1 = 0;
        int pStr2 = 0;
        return isRegularMatching(s1,s2,pStr1,pStr2);
    }

    public boolean isRegularMatching(char[] s,char[] p,int sPoint,int pPoint)
    {
        int sLength = s.length;
        int pLength = p.length;
        if(pLength == 0&&sLength == 0)return true;
        else if(pLength == 0) return false;
        else if(sLength == 0)
        {
            if((pPoint+1<pLength&&p[pPoint+1]=='*'))
            {
                if(pPoint + 2 == pLength)return true;
                else
                {
                    return isRegularMatching(s,p,sPoint,pPoint+2);
                }
            }
        }
        if(pPoint == pLength ) return sPoint == sLength;
        //if(sPoint == sLength) return pPoint == pLength;
        if(pPoint+1<pLength&&p[pPoint+1] == '*')
        {
            while((sPoint<sLength&&p[pPoint]=='.')||(sPoint<sLength&&pPoint<pLength&&s[sPoint] == p[pPoint]))
            {
                if(isRegularMatching(s,p,sPoint,pPoint+2))return true;
                sPoint++;
            }
            return isRegularMatching(s,p,sPoint,pPoint + 2);
        }
        else if((sPoint<sLength&&p[pPoint]=='.')||(sPoint<sLength&&pPoint<pLength&&s[sPoint] == p[pPoint]))
        {
            return isRegularMatching(s,p,sPoint+1,pPoint+1);
        }
        return false;
     }
}