My recursive cpp code using derivatives


  • 0
    C
    class Solution {
    public:
        // isMatch(a..., c<Re>) = false
        // isMatch(c..., c<Re>) = isMatch(..., <Re>)
        // isMatch(c..., .<Re>) = isMatch(..., <Re>)
        
        // isMatch(a..., c*<Re>) = isMatch(a..., <Re>)
        // isMatch(c..., c*<Re>) = isMatch(..., c*<Re>) || isMatch(c..., <Re>)
        // isMatch(c..., .*<Re>) = isMatch(..., .*<Re>) || isMatch(c..., <Re>)
        
        // isMatch(c..., "") = false
        // isMatch("", <Re>) = containNull(<Re>)
        
        // containNull(c<Re>) = false
        // containNull(c*<Re>) = containNull(<Re>)
        // containNull("") = true
        
        bool containNull(const string& p, int start, int end)
        {
            if(start == end) return true;
            if(end == start+1) return false;
            if(p[start+1] == '*') return containNull(p, start+2, end);
            return false;
        }
        
        bool isMatchHelper(const string& s, int s_start, int s_end,
                           const string& p, int p_start, int p_end)
        {
            if(s_start == s_end) return containNull(p, p_start, p_end);
            if(p_start == p_end) return false;
            
            if(p_start <= p_end-2 && p[p_start+1] == '*')
            {
                if(s[s_start] == p[p_start] || p[p_start] == '.')
                    return isMatchHelper(s, s_start+1, s_end, p, p_start, p_end)
                        || isMatchHelper(s, s_start, s_end, p, p_start+2, p_end);
                else
                    return isMatchHelper(s, s_start, s_end, p, p_start+2, p_end);
            }
            
            if(s[s_start] == p[p_start] || p[p_start] == '.')
                return isMatchHelper(s, s_start+1, s_end, p, p_start+1, p_end);
            else
                return false;
        }
    
        bool isMatch(string s, string p) 
        {
            return isMatchHelper(s, 0, s.size(), p, 0, p.size());
        }
    };

Log in to reply
 

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