Leetcode: Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

Using dynamic programming (instead of a matrix that keeps if s[0..row] matches p[0..col], but to reduce the space complexity we just need to keep the previous row).

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean []  previousLevel = new boolean[p.length()+1];
        previousLevel[0] = true;
        
        
        //Initialization
        for (int i=0; i<p.length(); i++)
            if(p.charAt(i)=='*')
                previousLevel[i+1]= previousLevel[i-1];
        
        for (int letter=0; letter<s.length(); letter++)
        {
            boolean []  thisLevel = new boolean[p.length()+1];
            for (int i=0; i<p.length(); i++)
            {
                if(p.charAt(i)=='.' || p.charAt(i)==s.charAt(letter))
                    thisLevel[i+1]= previousLevel[i];
                if(p.charAt(i)=='*')
                {
                    thisLevel[i+1] = thisLevel[i-1];
                    thisLevel[i+1] = thisLevel[i+1] || ( previousLevel[i+1] && (p.charAt(i-1)==s.charAt(letter)|| p.charAt(i-1)=='.'));
                }
            }
            previousLevel = thisLevel;
        }
        return previousLevel[p.length()];
    }
}