My 3ms C++ solution beats 100%


  • 0
    B
    class Solution {
    public:
    
    void  simpleStr(string & s)
    {
    	bool anyChar = false;
    	int i = 0, flag = -1, curAny = -1;
    	while (i + 1 < s.size())
    	{
    		if (s[i + 1] == '*')
    		{
    			if (flag == -1)
    			{
    				flag = i;
    			}
    			if (anyChar && i != curAny)
    			{
    				s.erase(i, 2);
    				if (i < curAny)
    				{
    					curAny -= 2;
    				}
    			}
    			else if (!anyChar && s[i] == '.')
    			{
    				anyChar = true;
    				curAny = i;
    				i = flag;
    			}
    			else if (!anyChar && i + 3 < s.size() && s[i + 3] == '*' && s[i] == s[i + 2])
    			{
    				s.erase(i, 2);
    			}
    			else
    			{
    				i += 2;
    			}
    		}
    		else
    		{
    			anyChar = false;
    			flag = -1;
    			curAny = -1;
    			i++;
    		}
    	}
    }
    
    bool isRecursiveMatch(string s, string p) {
    	int i = 0, j = 0;
    	if (p.size() == 0)
    	{
    		return (s.size() == 0);
    	}
    	bool anyChar = false;
    	
    	i = 0; j = 0;
    	while (i < s.size() || j < p.size())
    	{
    		anyChar = false;
    		if (j >= p.size())
    		{
    			return (i >= s.size());
    		}
    
    		if (p[j] == '.')
    		{
    			anyChar = true;
    		}
    		if (j + 1 < p.size() && p[j + 1] == '*')
    		{
    			int tempi = i;
    			while (tempi < s.size())
    			{
    				if (isRecursiveMatch(s.substr(tempi), p.substr(j + 2)))
    				{
    					return true;
    				}
    				if (!anyChar && s[tempi] != p[j])
    				{
    					i = tempi - 1;
    					break;
    				}
    				tempi++;
    			}
    			if (tempi == s.size())
    			{
    				return isRecursiveMatch("", p.substr(j + 2));
    			}
    			i++;
    		}
    		else
    		{
    			if( i >= s.size() || (!anyChar && s[i] != p[j]) )
    			{
    				return false;
    			}
    		}
    
    		i++;
    		j++;
    	}
    	return true;
    }
    bool isMatch(string s, string p)
    {
    	simpleStr(p);
    	return isRecursiveMatch(s, p);
    }
    };
    

Log in to reply
 

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