Regular Expression Matching

1. Problem Description

Given a 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 Matching means covering the entire string s, not only part of the string.

2. Approach

3. Implementation

package main

func isMatch(s string, p string) bool {
	return isMatchDFS(s, p)
}

func isMatchDFS(s string, p string) bool {
	if p == "" {
		return s == ""
	}

	isFirstMatch := len(s) > 0 && (p[0] == '.' || p[0] == s[0])
	isMatchAny := len(p) > 1 && p[1] == '*'

	if isMatchAny {
		return isMatchDFS(s, p[2:]) || (isFirstMatch && isMatchDFS(s[1:], p))
	} else {
		return isFirstMatch && isMatchDFS(s[1:], p[1:])
	}
}

4. References

• 10. Regular Expression Matching - LeetCode