*LeetCode 10 Regular Expression Matching 正则表达式

题目：

https://leetcode.com/problems/regular-expression-matching/

思路：

（1）DFS

（2）自动机

DFS版本写的比较烂，然后很长逻辑混乱，基本就是出bug补上。。。

592ms

const int DEBUG = 0;

class Solution {
public:
    bool match(char a,char b) {
        return (a == b || b == '.');
    }
    bool isMatch(string s,string p) {
       if(dfs(s,p,0))
            return true;
        return false;
    }
    bool check(string p,int pos) {
        if( (p.size()-pos) %2 == 0 ){
            for(int i=1+pos; i<p.size(); i+=2)
                if(p[i] != '*')return false;
            return true;
        }
        return false;
    }

    bool dfs(string s,string p,int pos) {
        if(s.size() == 0) {
            /*if( (pos == p.size()&&p[pos-1]!='*' ||
                 (pos == p.size()-1 && p[pos]=='*'))
               )return true;*/
            if( (pos == p.size()&&p[pos-1]!='*' ||
                 (check(p,pos+1) && p[pos]=='*'))
               )return true;
            //if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;
            if(check(p,pos))return true;
            if(DEBUG) {
                cout << "s.size() == 0 s=" << s << "  p=" << p << "  pos=" << pos << endl;
            }
            return false;
        }
        if(p.size() <= pos) {
            if(DEBUG) {
                cout << "p.size() <= pos s=" << s << "  p=" << p << "  pos=" << pos << endl;
            }
            return false;
        }
        int ptrs = 0,ptrp = pos;
        while(ptrs < s.size() && ptrp < p.size() ) {
            if( match(s[ptrs],p[ptrp]) ) {
                if(ptrp+2 < p.size() && p[ptrp+1] == '*') {
                    if(dfs(s.substr(ptrs),ptrp+2))return true;
                }
                ptrs ++,ptrp ++;
                continue;
            }
            if(p[ptrp] == '*') {
                if(ptrp >= 1) {
                    if( match(s[ptrs],p[ptrp-1]) ) {
                        return dfs(s.substr(ptrs+1),ptrp) | dfs(s.substr(ptrs),ptrp+1);
                        //   | 1 | 0
                    } else {
                        return dfs(s.substr(ptrs),ptrp+1);
                    }
                } else {
                    return false;
                }
                continue;
            } //else {
            if(ptrp+1 < p.size() && p[ptrp+1] == '*'){
                    //cout << "s=" << s.substr(ptrs) << "  p=" << p << "  " << ptrp+2 << endl;
                return dfs(s.substr(ptrs),ptrp+2);
            }
            else
                return false;
            //}
        }
        if( ptrs >= s.size()  ){
            pos = ptrp;
            //if( (pos == p.size()&&p[pos-1]!='*') || (pos == p.size()-1 && p[pos]=='*') )return true;
            //if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;

            if( (pos == p.size()&&p[pos-1]!='*' ||
                 (check(p,pos+1) && p[pos]=='*'))
               )return true;
            if(check(p,pos))return true;
            return false;

        }
        //if(ptrp >= p.size())return false;
        return false;
    }
};

正则表达式写法：很优雅，但是时间692ms，应该是因为某些可以用循环，但是这里还是递归了

class Solution {
public:
    bool isMatch(string s,string p) {
        return matchHere(s,p);
    }
    bool matchHere(string s,string p) {
        if(s.size() == 0) {
            return p.size()==0 || p.size()%2==0&&p[1]=='*'&&matchStar('',s,p.substr(2));
        }
        if(p.size() >=2 && p[1]=='*' && matchStar(p[0],p.substr(2)))
            return true;
        if(s[0] == p[0] || p[0] == '.') {
            return matchHere(s.substr(1),p.substr(1));
        }
        return false;
    }
    //c* and p has erased c*
    bool matchStar(char c,string s,string p){
        int ptr = -1;
        do {
            ++ptr;
            if(matchHere(s.substr(ptr),p))return true;
        } while( ptr<s.size() && ( s[ptr]==c || c=='.' ) );
        return false;
    }
};

正则表达式的写法参考：

http://hexlee.iteye.com/blog/552361

里面有^和&的处理方法

有空再去练习下怎么DFS写得优雅，比如http://blog.csdn.net/doc_sgl/article/details/12719761

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!