4ms o(n)space c++ solution


  • 0
    A

    The basic idea is to scan through expression p

    Use a vector<bool> match to record any substring that match the expression so far. Where match[i] means the first i chars match the expression.

    class Solution {
    public:
        bool isMatch(string s, string p) {
            vector<bool> match(s.size() + 1, false);
            match[0] = true;
            bool found;
            int a,i;
            
            int maxMatch = 0;
            for(a = 0; a < p.size();a++ )
            {
                //nothing match previous pattern
                if(maxMatch < 0) return false;
                //match "?*" pattern
                if(a+1 < p.size() && p[a+1] == '*')
                {
                    for(i = 0; i <= maxMatch ;i++)
                    {
                        if (!match[i]) continue;
                        else if(i < s.size() && (p[a] == '.' || p[a] == s[i]))
                        {
                            match[i+1] = true;
                            maxMatch = max(maxMatch,i+1);
                        }
                        
                    }
                    a++;
                    continue;
                }
                //match single char
                found = false;
                for(i = maxMatch; i >= 0 ; i--)
                {
                    if (!match[i]) continue;
                    if (i < s.size() &&(p[a] == '.' || p[a] == s[i]))
                    {
                        found = true;
                        match[i+1] = true;
                        match[i] = false;
                    }
                    else match[i] = false;
                }
                if(found) maxMatch++;
            }
            return match.back();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.