Given an input string (s) and a pattern (p), 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).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution:

func isMatch2(s string, p string) bool {
    if len(p) == 0 {
        return len(s) == 0
    }
    first_match := (len(s) != 0) && (p[0] == s[0] || p[0] == '.' )
    if len(p) >= 2 && p[1] == '*' {
        return isMatch(s,Slice(p,2))  || (first_match && isMatch(Slice(s,1), p))
    } else {
        return first_match && isMatch( Slice(s,1), Slice(p,1))
    }
}

func Slice(s string, index int) string {
    if len(s) > index {
        return s[index:]
    }else {
        return ""
    }
}

func isMatch(s string, p string) bool {
    lenS := len(s)
    lenP := len(p)
    
    dp := make([][]bool, lenS+1)
    for i:= 0; i <= lenS; i++ {
        dp[i] = make([]bool,lenP+1)
    }
    dp[0][0] = true
    for i:=0; i < lenP; i++ {
        if p[i] == '*'&& dp[0][i-1] {   //! important
            dp[0][i+1] = true
        }
    }
    for i:=0; i < len(s); i++ {
        for j:=0; j < len(p); j++ {
            switch {
                case p[j] == '.':
                    dp[i+1][j+1] = dp[i][j]
                    continue
                case p[j] == s[i]:
                    dp[i+1][j+1] = dp[i][j]
                    continue
                case p[j] == '*':
                if p[j-1] != s[i] && p[j-1] != '.' {
                    dp[i+1][j+1] = dp[i+1][j-1]
                } else {
                    dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]
                }
            }
        }
    }
    
    return dp[lenS][lenP]
    
}