O(mn) time and O(n) space, cpp, 4ms


  • 0
    C
    class Solution {
    public:
        bool isMatch(string s, string p)
        {
        	bool* bits = new bool[p.size()+1];
        	bool* bitsPrev = new bool[p.size()+1];
        	int i, j;
        	for(i = 0; i <= p.size(); i++) 
        		bitsPrev[i] = false;
        	for(j = 0;;)
        	{  char sc = j > 0 ? s[j-1] : 0;
        		for(i = 0; i <= p.size(); i++)
        		{  char pc = i > 0 ? p[i-1] : 0;
        			if((pc == '.' || pc == sc) && (i <= 0 || bitsPrev[i-1]))
        				bits[i] = true;
        			else if(pc == '*')
        			{	if(i <= 1 || bits[i - 2])
        					bits[i] = true;
        				else if((sc == p[i - 2] || p[i - 2] == '.') && (bits[i-1] || bitsPrev[i])) 
        					bits[i] = true;
        				else
        					bits[i] = false;
        			}
        			else
        				bits[i] = false;
        		}
        		if(++j > s.size())
        			break;
        		bool* tmp = bits; bits = bitsPrev; bitsPrev = tmp;
        	}
        	bool result = bits[p.size()];
        	delete[] bits;
        	delete[] bitsPrev;
        	return result;
        }
    };

  • 0
    F
    This post is deleted!

Log in to reply
 

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