Regular Expression Matching (. and *) bool IsMatch(string s, string p) { return IsMatchHelper(s, p, 0, 0); } bool IsMatchHelper(string s, string p, int i, int j) { if (j == p.Length) return i == s.Length; bool firstMatch = (i < s.Length) && (p[j] == s[i] || p[j] == '.'); if (j + 1 < p.Length && p[j + 1] == '*') { // Two cases: // 1) Use zero occurrence of p[j] (skip) // 2) If firstMatch, consume one char in s and keep pattern

return IsMatchHelper(s, p, i, j + 2) ||

}

{
return firstMatch && IsMatchHelper(s, p, i + 1, j + 1);
}

}