Tuesday, 18 October 2016

Regular Expression Matching (LeetCode)

Problem: Regular Expression Matching

class Solution {
public:
    int sl, pl;
    bool isMatch(string s, string p) {
        sl=s.length();
        pl=p.length();
        if(pl==0) return sl==0;
        return allMatch(s, 0, p, 0);
    }
    
    bool allMatch(string s, int scur, string p, int pcur)
    {
        //if(scur==sl) return pcur==pl;
        if(pcur==pl) return scur==sl;
        
        if(pcur+1<pl && p[pcur+1]=='*')
        {
            if(allMatch(s, scur, p, pcur+2)) 
                return true;
            if(p[pcur]=='.' || p[pcur]==s[scur])
            {
              while(scur<sl && (p[pcur]=='.' || p[pcur]==s[scur]))
                {
                    if(allMatch(s, scur+1, p, pcur+2)) 
                        return true;
                    scur++;
                    /*if(scur==sl)
                        break;*/
                }
            }
        }
        else if(p[pcur]=='.' || p[pcur]==s[scur]) 
            return allMatch(s, scur+1, p, pcur+1);
        return false;
    }
};

No comments:

Post a Comment